Dijkstra算法

Posted on |

求单源最短路径
dis 保存第i点到源点的最短距离

传统

用数组flag 记录集合 S,V-S

dis 记录与源点的距离

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

#include<stack>
#include <iostream>
#include <vector>
#include <queue>
#include<string.h> 
using namespace std;
int n;
#define MAX 100
#define INF 1e7
int dis[MAX];
bool flag[MAX];
int p[MAX];
//用P数组记录了最短路径上每一个节点的前驱 
int map[MAX][MAX];
void dij(int u){
	//初始化原点到其他路径最短长度 
	for(int i=1;i<=n;i++){
		if(map[u][i]!=INF) {
			dis[i]=map[u][i];
			p[i]=u;
		}
		else {
			p[i]=-1;
			dis[i]=INF;
		}
	}

	//初始化集合	
	flag[u]=true;
	dis[u]=0;
	for(int i=1;i<=n;i++)
	{
		int tmp=INF,t=u; 
		for(int k=1;k<=n;k++){

		if(!flag[k]&&tmp>dis[k]) {//!!
			
			tmp=dis[i];
			t=k;
		}
		
		}
		if(t==u) return;
		flag[t]=true;

		for(int j=1;j<=n;j++){
			
			if(!flag[j]&&map[t][j]<INF)//在图中 
			{
				if(map[t][j]+dis[t]<dis[j])
				{
				 
				dis[j]=map[t][j]+dis[t];
				p[j]=t;
				} 
			}
			
		}
	}
}
void findPath(int u){
	stack<int> s;

	for(int i=1;i<=n;i++){
			s.push(i);
		int x=p[i];
		
		while(x!=-1){
			s.push(x);
			x=p[x];
		}
		cout<<u<<"到"<<i<<"的路径为:"<<endl; 
		while(!s.empty()){
			cout<<s.top()<<" "; 
			s.pop();
		}
		cout<<endl;
		
	} 
	
	
} 
int main(){
	int m,u,v,w;
	freopen("11.txt","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
		map[i][j]=INF;
	}
	cin>>m;
	memset(flag,false,sizeof(flag));
	for(int i=1;i<=m;i++){
		//城市1 城市2 距离 
		cin>>u>>v>>w;
		map[u][v]=min(map[u][v],w);
		
	}
	int src;
	cin>>src;
	dij(src);
	for(int i=1;i<=n;i++){
		cout<<src<<"到"<<i<<"点距离 "<<dis[i]<<endl;
		
		
	} 
	for(int i=1;i<=n;i++){
		cout<<p[i]<<" ";
	}
	cout<<endl;
	findPath(src);
	
}

使用优先队列

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
#include<string.h> 
#include<stack>
#include<queue>
#include<iostream> 
#define MAX 100
#define INF 1e7
using namespace std;
int dis[MAX];
bool flag[MAX];
int p[MAX];
//用P数组记录了最短路径上每一个节点的前驱 
int map[MAX][MAX];
int n;
struct node{
	int c;
	int v;
	node(int cc,int vv):c(cc),v(vv){
	}
	bool operator <(const node &p)const{
		return v>p.v;
	}
};


void dij(int u){
	//初始化原点到其他路径最短长度 
	for(int i=1;i<=n;i++){
		if(map[u][i]!=INF) {
			
			p[i]=u;
		}
		else {
			p[i]=-1;
		
		}
			dis[i]=INF;
	}
	dis[u]=0;
	priority_queue<node> pq;
	pq.push(node(u,0));
	while(!pq.empty()){
		node t=pq.top();
		pq.pop();
		for(int i=1;i<=n;i++){
			if(map[t.c][i]!=INF){
				if(map[t.c][i]+dis[t.c]<dis[i])
				{
					dis[i]=map[t.c][i]+dis[t.c];
					p[i]=t.c;
					pq.push(node(i,dis[i]));
				}
			}
			
			
		}
		
		
	}
	
	
}
void findPath(int u){
	stack<int> s;

	for(int i=1;i<=n;i++){
			s.push(i);
		int x=p[i];
		
		while(x!=-1){
			s.push(x);
			x=p[x];
		}
		cout<<u<<"到"<<i<<"的路径为:"<<endl; 
		while(!s.empty()){
			cout<<s.top()<<" "; 
			s.pop();
		}
		cout<<endl;
		
	} 
	
	
} 
int main(){
	int m,u,v,w;
	freopen("11.txt","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
		map[i][j]=INF;
	}
	cin>>m;
	memset(flag,false,sizeof(flag));
	for(int i=1;i<=m;i++){
		//城市1 城市2 距离 
		cin>>u>>v>>w;
		map[u][v]=min(map[u][v],w);
		
	}
	int src;
	cin>>src;
	dij(src);
	for(int i=1;i<=n;i++){
		cout<<src<<"到"<<i<<"点距离 "<<dis[i]<<endl;
		
		
	} 
	for(int i=1;i<=n;i++){
		cout<<p[i]<<" ";
	}
	cout<<endl;
	findPath(src);
	
}

image

复习

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
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#define MAX 1000
#define INF 0x3f3f3f
using namespace std;
bool vis[MAX];
int n,m,st,ed;
int p[MAX],ids;
//用P数组记录了最短路径上每一个节点的前驱 
int map[MAX][MAX],dis[MAX],w[MAX];
struct node{
	int v,c;
	node(int vv,int cc):c(cc),v(vv){
		
	}
	bool operator <(const node&p)const{
	return c>p.c;
	}
};
void dij(int src,int ed){
	for(int i=0;i<n;i++)
	{
		dis[i]=INF;
		p[i]=-1; 
	}
	dis[src]=0;
	priority_queue<node> pq;
	pq.push(node(src,0));
	while(!pq.empty()){
		node t=pq.top();
		pq.pop();
		if(dis[t.v]<t.c) continue;
		if(t.v==ed) break;
		for(int i=0;i<n;i++){
			if(map[t.v][i]!=INF){
				if(map[t.v][i]+dis[t.v]<dis[i])
				{
					dis[i]=map[t.v][i]+dis[t.v];
					p[i]=t.v;
					pq.push(node(i,dis[i]));
				}
			}	
		}
	}
	
	
	
	
}
int main(){
	cin>>n>>m>>st>>ed;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		map[i][j]=INF; 
	 } 
	 for(int i=0;i<m;i++){
	 	int a,b;
	 	cin>>a>>b;
	 	cin>>map[a][b];
	 	map[b][a]=map[a][b];
	 }
	dij(st,ed);
	cout<<dis[ed]<<endl;
}

参考链接
用领接表 优先队列实现:
http://www.voidcn.com/article/p-pwheyixu-te.html