Dijkstra算法求带权图的单源最短路径

Dijkstra算法求带权图的单源最短路径

Dijkstra可以用来求不带负权的带权图
Dijkstra的核心是松弛操作,具体松弛操作是什么,请看代码吧。
使用索引堆优化过的Dijkstra算法的时间复杂度为$O(Elog(V))$

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
package ShortestPath;

import java.util.Stack;
import java.util.Vector;

/**
* @ Description: Dijkstra求有权图的最短路径
* @ Date: Created in 13:01 2018/8/2
* @ Author: Anthony_Duan
*/
public class Dijkstra<Weight extends Number & Comparable> {
//图的引用
private WeightedGraph G;
//起始点
private int s;
//distTo[i]存储从起始点s到i的最短路径长度
private Number[] distTo;
// 标记数组,在算法运行过程中标记节点i是否被访问
private boolean[] marked;

//form[i]记录最短路径中到达i点的边是哪一条
//可以用来恢复整个最短路径
private Edge<Weight>[] from;


//构造函数,使用Dijkstra算法求最短路径
public Dijkstra(WeightedGraph graph, int s) {

//算法初始化
G = graph;
assert s >= 0 && s < G.V();
this.s = s;
distTo = new Number[G.V()];
marked = new boolean[G.V()];
from = new Edge[G.V()];
for (int i = 0; i < G.V(); i++) {
distTo[i] = 0.0;
marked[i] = false;
from[i] = null;
}

//使用索引堆记录当前找到的到达每个顶点的最短距离
IndexMinHeap<Weight> ipq = new IndexMinHeap<>(G.V());

//对于其点s进行初始化
distTo[s] = 0.0;
from[s] = new Edge<>(s, s, (Weight) (Number) (0.0));
//先把初始点放入堆中
ipq.insert(s, (Weight) distTo[s]);

marked[s] = true;

while (!ipq.isEmpty()) {
int v = ipq.extractMinIndex();

// distTo[v]就是s到v的最短距离
marked[v] = true;

// 对v的所有相邻节点进行更新
for (Object item :
G.adj(v)) {
Edge<Weight> e = (Edge<Weight>) item;
int w = e.other(v);
//如果从s点到w点的最短路径还没有找到
if (!marked[w]) {
// 如果w点以前没有访问过
//或者访问过但是通过当前v点到w点距离更短,则进行更新
if (from[w] == null || distTo[v].doubleValue() + e.wt().doubleValue() < distTo[w].doubleValue()) {
distTo[w] = distTo[v].doubleValue() + e.wt().doubleValue();
from[w] = e;
if (ipq.contain(w)) {
ipq.change(w, (Weight) distTo[w]);
}else {
ipq.insert(w,(Weight)distTo[w]);
}
}
}
}
}
}


//返回从s点到w点的最短路径长度
Number shortestPathTo(int w) {
assert w >= 0 && w < G.V();
assert hasPathTo(w);
return distTo[w];
}

//判断从s点到w点是否联通
boolean hasPathTo(int w) {
assert w >= 0 && w < G.V();
return marked[w];
}

//寻找从s到w的最短路径,将整个路径经过的边存放在vec中
Vector<Edge<Weight>> shortestPath(int w) {
assert w >= 0 && w < G.V();
assert hasPathTo(w);

//通过from数组逆向查找从s 到w的路径,存放到栈中
Stack<Edge<Weight>> s = new Stack<>();
Edge<Weight> e = from[w];
while (e.v() != this.s) {
s.push(e);
e = from[e.v()];
}
s.push(e);

//从栈中一次取出元素,获得顺序的从s到w的路径
Vector<Edge<Weight>> res = new Vector<>();
while (!s.isEmpty()) {
e = s.pop();
res.add(e);
}
return res;
}

//打印出从s到w点的路径
void showPath(int w) {
assert w >= 0 && w < G.V();
assert hasPathTo(w);


Vector<Edge<Weight>> path = shortestPath(w);
for (int i = 0; i < path.size(); i++) {
System.out.print(path.elementAt(i).v() + " ->");
if (i == path.size() - 1) {
System.out.println(path.elementAt(i).w());
}
}
}


// 测试我们的Dijkstra最短路径算法
public static void main(String[] args) {

String filename = "/Users/duanjiaxing/IdeaProjects/Algorithm/src/ShortestPath/testG1.txt";
int V = 5;

SparseWeightedGraph<Integer> g = new SparseWeightedGraph<Integer>(V, true);
// Dijkstra最短路径算法同样适用于有向图
//SparseGraph<int> g = SparseGraph<int>(V, false);
ReadWeightedGraph readGraph = new ReadWeightedGraph(g,filename);

System.out.println("Test Dijkstra:\n");
Dijkstra<Integer> dij = new Dijkstra<Integer>(g,0);
for( int i = 1 ; i < V ; i ++ ){
if(dij.hasPathTo(i)) {
System.out.println("Shortest Path to " + i + " : " + dij.shortestPathTo(i));
dij.showPath(i);
}
else {
System.out.println("No Path to " + i );
}

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

}
}
-------------End Of This ArticleThank You For Reading-------------