Dijkstra算法，最小優(yōu)先隊(duì)列用堆(Heap)實(shí)現(xiàn) 偽代碼描述 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 最基本的二叉堆是實(shí)現(xiàn)不了的，因?yàn)閐ijkstra要求在運(yùn)行過(guò)程中隨時(shí)修改堆內(nèi)元素，因此要用擴(kuò)展版的、引入了外部指針的二叉堆
3 另外，當(dāng)圖用鄰接表來(lái)表示的時(shí)候，用二叉堆的時(shí)間復(fù)雜度為O(ElgV)，不用二叉堆的復(fù)雜的是O(V^2)；不用鄰接表的時(shí)候，用二叉
4 堆時(shí)間復(fù)雜度為O(V^2lgV)，不用二叉堆的時(shí)間復(fù)雜度為O(V^2)。也就是說(shuō)，只有當(dāng)使用鄰接表來(lái)表示稀疏圖的時(shí)候，使用二叉堆才
5 有效率優(yōu)勢(shì)。因此本程序使用鄰接表來(lái)表示圖
6 */
7 #include <stdio.h>
8#include <iostream>
9#define INF 0xfffffff
10#define MAXN 100
11
12using namespace std;
13
14int deg[MAXN]; // 節(jié)點(diǎn)i的度
15int list[MAXN][MAXN][2]; // list[i][j][1]：節(jié)點(diǎn)i第j個(gè)鄰接節(jié)點(diǎn)在list中的下標(biāo),list[i][j][2]表示它們之間的距離
16int heap[MAXN]; // 堆，heap[i]存儲(chǔ)的是節(jié)點(diǎn)的編號(hào)
17int key[MAXN]; // 堆中元素的值,算法結(jié)束時(shí)為各點(diǎn)到源s的最短路的值
18int pos[MAXN]; // pos[i]表示第i個(gè)節(jié)點(diǎn)在堆中的位置
19int count; // 未找到最短路徑的節(jié)點(diǎn)數(shù)目，也是堆的大小
20bool exist[MAXN]; // 標(biāo)識(shí)節(jié)點(diǎn)i是否還未找到最短路
21int n; // 結(jié)點(diǎn)數(shù)
22int trace[MAXN]; // 存放最短路的路徑
23// 交換兩個(gè)整數(shù)
24void swap(int &a,int &b)
25 {
26 int tmp=a;
27 a=b;
28 b=tmp;
29}
30// 向下調(diào)整
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// 向上調(diào)整
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// 找到當(dāng)前離source最近的點(diǎn)，返回它的編號(hào)
58int extract()
59{
60 int tmp=heap[1];
61 if(count>1) siftdown(1);
62 return tmp;
63}
64// 修改編號(hào)為id的結(jié)點(diǎn)在堆中的值，并調(diào)整堆
65void relax(int u)
66{// 若d[u]+dis[u][v]<d[v]，則修改d[v]為d[u]+dis[u][v];u為剛從堆中彈出的點(diǎn)，有向邊(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 // 初始時(shí)堆Q中存放所有的節(jié)點(diǎn)
90 count=n;
91 key[1]=0;
92 while(count>0)
93 {
94 int id=extract(); // 當(dāng)前距離節(jié)點(diǎn)1最近的點(diǎn)提出來(lái)并修改所有與它鄰接的點(diǎn)
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}
|