dijkstra算法也是采用的贪心算法,和prim算法非常像,可以比较一下代码,就两三行不同。

思想就是根据各顶点到源点的距离生成一个优先级队列,初始时除了源点距离为零,其它都为INF。这样,每次从队列中取出最短路径的顶点,然后对每个邻接的顶点进行松弛,更新队列。重复操作直至队列为空。

伪代码如下:

1
2
3
4
5
6
7
8
9
DIJKSTRA(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
S <- null
Q <- V[G]
while Q != null
do u <- EXTRACT-MIN(Q)
S <- S + u
for each vertex v in Adj[u]
do RELAX(u, v, w)

当然,在实现的过程中,并没有按照伪代码所写的流程来,因为要更新优先级队列中的值很麻烦,所以采取了prim算法中所使用的方法。

dijkstra算法由于是贪心算法,所以图中不能有负权值的边。

比如

1
2
3
4
5
6
1 -- 1 --> 2
| |
100 2
| |
﹀ ﹀
3 -- -99 --> 4

在上面的图中,我们最后会得到1->4的距离为3,而不是1.

dijkstra算法和prim算法的区别很小,一个在于key中存储的是最短路径,另一个存储的是与其邻接的最小的边。

操作上的不同就是在prim中,直接用邻接的边去更新key的值,而dijkstras中是松弛一条边,然后根据松弛的结果更新key的值。

代码如下:

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
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 10000
#define NIL -1
#define MAX_V 1000 //最大顶点数
int G[MAX_V][MAX_V]; //图
int N; //顶点个数
//节点
struct Node {
Node(int vertex = 0, int key = INF) : vertex(vertex), key(key) {}
int vertex;
int key;
};
class MinHeap
{
public:
bool operator() (const Node *a, const Node *b) const
{
return (a->key > b->key);
}
};
void dijkstra() {
priority_queue<Node *, vector<Node *>, MinHeap> Q;
vector<int> P(N, -1);
vector<int> keys(N, INF);
//初始化第一个元素
Q.push(new Node(0, 0));
keys[0] = 0;
while (!Q.empty()) {
Node *top = Q.top();
Q.pop();
if (top->key > keys[top->vertex]) continue;
for (int i = 0; i < N; i++) {
if (G[top->vertex][i] != 0 && G[top->vertex][i] != INF) {
if ((top->key + G[top->vertex][i]) < keys[i]) {
keys[i] = top->key + G[top->vertex][i];
P[i] = top->vertex;
Q.push(new Node(i, keys[i]));
}
}
}
}
}
int main() {
/* example input
5
0 10 10000 5 10000
10000 0 1 2 10000
10000 10000 0 10000 4
10000 3 9 0 2
7 10000 6 10000 0
*/
cin>>N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int w;
cin>>w;
G[i][j] = w;
}
}
dijkstra();
}