Dijkstra算法，最小優先隊列用堆(Heap)實現 偽代碼描述 void dijkstra() { Q=V; S={}; // 空集 while(Q!={}) { v = ExtractMin(Q); S = S + {v}; Q = Q - {v}; for all edge(v,u), relax the edge; // if(d[v] + dis[v][u] < d[u]) d[u] = d[v] + dis[v][u]; } }
1  /**//*
2 最基本的二叉堆是實現不了的，因為dijkstra要求在運行過程中隨時修改堆內元素，因此要用擴展版的、引入了外部指針的二叉堆
3 另外，當圖用鄰接表來表示的時候，用二叉堆的時間復雜度為O(ElgV)，不用二叉堆的復雜的是O(V^2)；不用鄰接表的時候，用二叉
4 堆時間復雜度為O(V^2lgV)，不用二叉堆的時間復雜度為O(V^2)。也就是說，只有當使用鄰接表來表示稀疏圖的時候，使用二叉堆才
5 有效率優勢。因此本程序使用鄰接表來表示圖
6 */
7 #include <stdio.h>
8#include <iostream>
9#define INF 0xfffffff
10#define MAXN 100
11
12using namespace std;
13
14int deg[MAXN]; // 節點i的度
15int list[MAXN][MAXN][2]; // list[i][j][1]：節點i第j個鄰接節點在list中的下標,list[i][j][2]表示它們之間的距離
16int heap[MAXN]; // 堆，heap[i]存儲的是節點的編號
17int key[MAXN]; // 堆中元素的值,算法結束時為各點到源s的最短路的值
18int pos[MAXN]; // pos[i]表示第i個節點在堆中的位置
19int count; // 未找到最短路徑的節點數目，也是堆的大小
20bool exist[MAXN]; // 標識節點i是否還未找到最短路
21int n; // 結點數
22int trace[MAXN]; // 存放最短路的路徑
23// 交換兩個整數
24void swap(int &a,int &b)
25 {
26 int tmp=a;
27 a=b;
28 b=tmp;
29}
30// 向下調整
31void siftdown(int index)
32{
33 pos[heap[count]]=pos[heap[index]];
34 heap[index]=heap[count];
35 int i=index,j;
36 while(2*i<=count)
37  {
38 j=2*i;
39 if(key[heap[j+1]]<key[heap[j]] && j+1<=count) j++;
40 if(key[heap[j]]>=key[heap[i]]) break;
41 swap(pos[heap[i]],pos[heap[j]]);
42 swap(heap[i],heap[j]);
43 i=j;
44 }
45}
46// 向上調整
47void siftup(int index)
48{
49 int i=index;
50 while(i>1 && key[heap[i]]<key[heap[i/2]])
51 {
52 swap(pos[heap[i]],pos[heap[i/2]]);
53 swap(heap[i],heap[i/2]);
54 i/=2;
55 }
56}
57// 找到當前離source最近的點，返回它的編號
58int extract()
59{
60 int tmp=heap[1];
61 if(count>1) siftdown(1);
62 return tmp;
63}
64// 修改編號為id的結點在堆中的值，并調整堆
65void relax(int u)
66{// 若d[u]+dis[u][v]<d[v]，則修改d[v]為d[u]+dis[u][v];u為剛從堆中彈出的點，有向邊(u,v)
67 for(int i=0;i<deg[u];i++)
68 {
69 if(exist[list[u][i][0]] == true && key[u]+list[u][i][1]<key[list[u][i][0]])
70 {
71 key[list[u][i][0]]=key[u]+list[u][i][1];
72 trace[list[u][i][0]]=u;
73 int p=pos[list[u][i][0]];
74 siftup(p);
75 }
76 }
77}
78
79void dijkstra()
80{
81 int i,j,k;
82 for(i=1;i<=n;i++)
83 {
84 heap[i]=i;
85 exist[i]=true;
86 pos[i]=i; // 源為1
87 key[i]=INF;
88 }
89 // 初始時堆Q中存放所有的節點
90 count=n;
91 key[1]=0;
92 while(count>0)
93 {
94 int id=extract(); // 當前距離節點1最近的點提出來并修改所有與它鄰接的點
95 count--;
96 exist[id]=false;
97 relax(id);
98 }
99 return;
100}
101
102int main()
103{
104 freopen("test.txt","r",stdin);
105 scanf("%d",&n);
106 count=n;
107 for(int i=1;i<=n;i++)
108 {
109 scanf("%d",°[i]);
110 for(int j=0;j<deg[i];j++)
111 {
112 scanf("%d%d",&list[i][j][0],&list[i][j][1]);
113 }
114 }
115 dijkstra();
116 for(i=1;i<=n;i++) printf("node %d precessor %d length %d\n",i,trace[i],key[i]);
117 return 1;
118}
|