算法: Johnson 算法是什么?
来源:简书 发布时间:2020-05-21 14:24:29

全源最短路径求解其实是单源最短路径的推广,求解单源最短路径的两种算法时间复杂度分别为:

Dijkstra 单源最短路径算法:时间复杂度为 O(E + VlogV),要求权值非负;

Bellman-Ford 单源最短路径算法:时间复杂度为 O(VE),适用于带负权值情况;

如果对全图顶点遍历,使用Dijkstra 算法,时间复杂度将变成O(VE + V2logV),看起来优于 Floyd-Warshall 算法的 O(V3)。不过,Dijkstra 算法要求权值重不能为负。

Johnson 算法能调整权重为负的图,使之能够使用Dijkstra 算法。

re-weight

以下图为例,Johnson 算法对下图进行re-weight操作,使权重不为负,并且re-weight后,计算出来的最短路径仍然正确。

首先,新增一个源顶点 ,并使其与所有顶点连通,新边赋权值为 0,如下图所示。

接下来重新计算新增顶点到其它顶点的最短路径,利用单源最短路径算法,图中存在负权重节点,使用bellman ford算法,计算新增节点到其它节点的最短路径 h[],然后使用如下公式对所有边的权值进行 "re-weight":

w(u, v) = w(u, v) + (h[u] - h[v]).

对于此公式的证明请参考算法导论一书。

现在除新增结点外,其它结点的相关边权重值都已经为正数了,可以将新增结点删除,对其它结点使用Dijkstra 算法了。

实现

Johnson 算法比Floyd-warshall算法更容易理解一些,实现较简单,代码如下。本博中所有代码均可见本人的github,欢迎访问。

undefined

public void johnson(MatrixGraph graph){

Vertex s = new Vertex("s");

graph.addVertex(s);

for (int i = 0; i < graph.mList.size(); i++) {

graph.addEdge(s, graph.mList.get(i), 0);

}

//计算s点到其它点的最短距离

ArrayList h = bellman_ford(graph, s);

//重新计算除s以外的其它点权重

ArrayList edges = new ArrayList<>();

MatrixEdge temp = null;

for (int i = 0; i < VERTEX_NUM; i++) {

for (int j = 0; j < VERTEX_NUM; j++) {

temp = graph.mEdges[i][j];

if (temp != null && temp.v1 != s && temp.v2 != s) {

edges.add(temp);

}

}

}

System.out.println(" -------- ");

for (int i = 0; i < edges.size(); i++) {

temp = edges.get(i);

temp.weight = temp.weight + h.get(graph.mList.indexOf(temp.v1)) - h.get(graph.mList.indexOf(temp.v2));

System.out.print(temp + " | ");

}

System.out.println();

System.out.println(" --------- ");

graph.removeVertex(s);

//根据重新计算的非负权重值,遍历调用dijkstra算法

for (int i = 0; i < graph.mList.size(); i++) {

dijkstra(graph, graph.mList.get(i));

}

}

作者:某昆

标签: johnson算法

猜你喜欢

碳中和板块暴涨8%再成市场焦点 碳达峰、碳中和

相信大家也都发现了,今天同花顺板块涨幅榜中增加了一个全新概念板块,那就是碳中和。碳中和板块上...更多

2021-03-02 16:37:47

黄金期货和白银期货均维持在短期支撑位之上

周三(1月13日)亚市盘中,黄金期货维持升势,现报1859美元 盎司附近。Kshitij咨询服务团队(Kshitij...更多

2021-01-13 16:54:56

老师教孩子怀孕和性别方面知识被家长吐槽 你怎么

最近,有网友在短视频平台上分享自己的经历。这位学生的家长觉得,自己的女儿才9岁,老师不应该教给...更多

2020-09-22 16:18:15

这四种大米一定不能买 消费者要远离这些“有毒大

大米是我们生活中必不可少的食物,在南方一日三餐是少不了大米的。而挑选优质的大米,这是很重要的...更多

2020-09-17 15:45:36

车险改革9月19日实施,这些利好你知道吗

机动车辆保险与百姓生活和切身利益关系密切,长期以来是财险领域第一大业务,社会关注度高。我国车...更多

2020-09-14 16:21:17

创业板注册制来了 交易技巧有哪些

8月24号开始,创业板注册制新股上市,同时老股也将实施20%的涨跌幅!!!依据科创板交易一年来的经验,...更多

2020-09-10 11:00:47

农房拆迁多少钱一平米 这些补偿标准一定要了解

伴随着国家城市化的发展,城市的需求土地量越来越大,很多城市为了发展需要,征用了周边农村的土地...更多

2020-09-09 14:45:53

制止餐饮浪费相关措施将尽快出台 行勤俭节约

数据指出,现在很多人外出就餐的时候,都是很浪费的,因为点了很多食物,但是吃不完,也不打包带走...更多

2020-08-28 15:54:24

期货怎么止盈? 设置期货止盈的技巧有哪些?

期货止盈,是指在期货上获取了一定盈利后,进行平仓的操作方法。俗话说:会买的是个好徒弟,会卖的...更多

2020-08-18 14:01:46

北京力推“夜经济” 激发消费新活力 助力旅游业

目前正值暑假,在北京,不少景区还大力打造夜间游玩项目,助力旅游业回暖。晚上8时20分,上百盏无人...更多

2020-08-12 16:39:01