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}
|