最短路径算法

最短路径

主要思想

1
2
3
4
5
6
7
8
Dijkstra算法采用的是一种贪心的策略,
声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合:T
初始时,原点 s 的路径权重被赋为 0 (dis[s] = 0)。
若对于顶点 s 存在能直接到达的边(s,m),则把dis[m]设为w(s, m),
同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大。初始时,集合T只有顶点s
然后,从dis数组选择最小值,则该值就是源点s到该值对应的顶点的最短路径,并且把该点加入到T中,此时完成一个顶点
然后,我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短,
如果是,那么就替换这些顶点在dis中的值。 然后,又从dis中找出最小值,重复上述动作,直到T中包含了图的所有顶点。

实例:HDUOJ2544 四种不同算法理解最短路径

1.迪杰斯特拉(Dijkstra)算法

算法原理:

1
2
3
原理:这里不进行严格证明,Dijkstra的大致思想就是,
根据初始点,挨个的把离初始点最近的点一个一个找到并加入集合,
集合中所有的点的d[i]都是该点到初始点最短路径长度,由于后加入的点是根据集合S中的点为基础拓展的,所以也能找到最短路径。

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
115
116
117
118
//代码实现:
#include <iostream>
using namespace std;
const int Inf = 1e9;
int Map[100 + 10][100 + 10];//存储权值的,即Map[i][j] 有i到j的距离
int flag[100 + 10];//存储的是个个点是否已经找到最短路径
int dis[100 + 10];//由初始点到各个点的最短路径
int dj(int m) {
int Max = Inf;
int dy = 0;
for (int i = 1; i <= m; i++) {//一共m个点一个一个找


for (int k = 1; k <= m; k++) {//找到现在为止离初始点最短的距离
if (Map[1][k] < Max && !flag[k]) {
Max = Map[1][k];//记录大小
dy = k;//记录位置
}
}
flag[dy] = 1;//表示该点已经找到最短路径
dis[dy] = Map[1][dy];//存储最最短路径
for (int k = 1; k <= m; k++) { //找到经过dy点且在dy临近的点离初始点的最短距离
if (!flag[k]&&Map[1][k] > dis[dy] + Map[dy][k]) {
Map[1][k] = dis[dy] + Map[dy][k];
}
}
dy = 0;
Max = Inf;
}
return dis[m];
}

int main() {
int m, n, a, b, c, s;
while (cin >> m >> n && m || n) {
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= m; j++) {
Map[i][j] = Inf;
}
}
memset(flag, 0, sizeof(flag));
for (int i = 0; i < n; i++) {
cin >> a >> b >> c;
if (Map[a][b] > c) {
Map[a][b] = c;
Map[b][a] = c;
}
}
cout << dj(m) << endl;
}
return 0;
}



//另一种写法:
#include<iostream>
#include<cstring>
using namespace std;
const int mod = 1e9;
const int maxx = 1e3;
const int INF = 0x3f3f3f3f;
int dis[maxx];
bool vis[maxx];
int map[maxx][maxx];
int dj(int x, int n)
{
int p;
for(int i = 1; i <= n; i ++)
dis[i] = map[1][i];
memset(vis, 0, sizeof vis);
vis[x] = 1;
for(int i = 1; i <= n ; i ++)
{
int minn = INF;
for(int j = 1; j <= n; j ++)
{
if(!vis[j] && dis[j] < minn)
{
minn = dis[j];
p = j;
}
}
vis[p] = 1;
for(int j = 1; j <= n; j ++)
{
if(!vis[j] && dis[p] + map[p][j] < dis[j])
dis[j] = dis[p] + map[p][j];
}
}
}
int main()
{
int n, m;
int a, b, c;
while(~scanf("%d%d",&n,&m))
{
if(n == 0 && m == 0) break;
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
map[i][j] = INF;
}
}
memset(vis, 0, sizeof vis);
for(int i = 1; i <= m; i ++)
{
cin >> a >> b >> c;
if(map[a][b] > c)
map[a][b] = map[b][a] = c;
}
dj(1, n);
cout << dis[n] << endl;
}

return 0;
}

另一种写法:

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
思想:每次找到离源点(如1号结点)最近的一个顶点,然后以该顶点为中心进行扩展,
最终得到源点到其余所有点的最短路径。

步骤:1.开容器v,储存子节点、距离、花费;2、开数组dis记录起始点到各点距离;
3、进行n-1次松弛操作(先找出未标记点中离起始点最近的点,标记该点,然后求出该点子节点到起始点的最短距离(优先)与最短花费);
4、输出到终点的最短距离与花费;

#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
#define N 999999999
using namespace std;

struct node{
int er,len,cost;
};
vector<node>v[1111];

int main()
{
int n,m;

while(~scanf("%d%d",&n,&m)&&n&&m)
{
int dis[1111],spend[1111];
bool vis[1111];
node tmp;
int x,y;
for(int i=0;i<1111;i++)
v[i].clear();
while(m--){
scanf("%d%d%d%d",&x,&y,&tmp.len,&tmp.cost);
tmp.er=x;
v[y].push_back(tmp);
tmp.er=y;
v[x].push_back(tmp);
}
scanf("%d%d",&x,&y);//起点和终点
for(int i=1;i<=n;i++){
vis[i]=0;
dis[i]=spend[i]=N;
}
for(int i=0;i<v[x].size();i++){
dis[v[x][i].er]=v[x][i].len;
spend[v[x][i].er]=v[x][i].cost;
}
vis[x]=1;
for(int k=1;k<=n-1;k++)
{
int id,mi=N;
for(int i=1;i<=n;i++){
if(!vis[i]&&dis[i]<mi){//查询并记录离x最近的点
id=i;mi=dis[i];
}
}
vis[id]=1;//标记过的点已经是最短
for(int i=0;i<v[id].size();i++)
{
int vv=v[id][i].er;
if(!vis[vv]&&dis[vv]>dis[id]+v[id][i].len)//未标记、直接距离大于通过id点的距离
dis[vv]=dis[id]+v[id][i].len,
spend[vv]=spend[id]+v[id][i].cost;

else if(!vis[vv]&&dis[vv]==dis[id]+v[id][i].len&&spend[vv]>spend[vv]+v[id][i].cost)//未标记、距离相等找花费更小的
spend[vv]=spend[id]+v[id][i].cost;
}
}
printf("%d %d\n",dis[y],spend[y]);
}

return 0;
}

2.Floyd算法

弗洛伊德算法(解决多源最短路径):时间复杂度O(n^3),空间复杂度O(n^2)

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
思想:最开始只允许经过1号顶点进行中转,接下来只允许经过1号和2号顶点进行中转......
允许经过1~n号所有顶点进行中转,来不断动态更新任意两点之间的最短路程。
即求从i号顶点到j号顶点只经过前k号点的最短路程。
#include<iostream>
#include<string.h>
#define inf 99999999
using namespace std;

int n,dis[111][111];
void init(){
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++)
dis[i][j]=inf;
dis[i][i]=0;
}
}
int main()
{
int m;
while(~scanf("%d%d",&n,&m)&&n&&m)
{
init();
while(m--){
int x,y,len;
scanf("%d%d%d",&x,&y,&len);

dis[x][y]=min(dis[x][y],len);
dis[y][x]=dis[x][y];
}
for(int k=1;k<=n;k++)//要经过的点
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
printf("%d\n",dis[1][n]);//可以选任意两点之间的距离
}
return 0;
}

3.DFS/BFS算法

深度或广度优先搜索算法(解决单源最短路径)

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
从起始结点开始访问所有的深度遍历路径或广度优先路径,则到达终点结点的路径有多条,取其中路径权值最短的一条则为最短路径。
给定一个带权有向图G=(V,E),其中每条边的权是一个实数。另外,还给定V中的一个顶点,称为
源。
现在要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通
常称为单源最短路径 [1] 问题。
从起始结点开始访问所有的深度遍历路径或广度优先路径,则到达终点结点的路径有多条,取其中路
径权值最短的一条则为最短路径

#include<iostream>
#include<string.h>
#define inf 99999999
using namespace std;

int dis[111][111];
bool vis[111];
int n,cnt;//n为节点数,cnt为最短长度

void init(int x){
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++)
dis[i][j]=inf;
dis[i][i]=0;
vis[i]=0;
}
}
void dfs(int st,int dst)
{
if(dst>cnt)return ;//距离大于最短路径,无需遍历
if(st==n){//到达终点
cnt=cnt>dst?dst:cnt;

return;
}
for(int i=1;i<=n;i++)
{
if(!vis[i]&&dis[st][i]!=inf&&dis[st][i]){
vis[i]=1;
dfs(i,dst+dis[st][i]);
vis[i]=0;
}
}
}

int main()
{
int m;
while(~scanf("%d%d",&n,&m)&&n&&m)
{
int x,y,len;

cnt=inf;
init(n);
while(m--){
scanf("%d%d%d",&x,&y,&len);
dis[x][y]=min(dis[x][y],len);//两点之间距离重复输入取小距离
dis[y][x]=dis[x][y];
}
vis[1]=1;
dfs(1,0);
printf("%d\n",cnt);
}
return 0;
}

4.Bellman-Ford

Bellman-Ford算法(解决负权边,解决单源最短路径,前几种方法不能求含负权边的图)::时间复杂度O(nm),空间复杂度O(m)

1
2
3
4
主要思想:对所有的边进行n-1轮松弛操作,因为在一个含有n个顶点的图中,任意两点之间的最短路径最多包含n-1边。
换句话说,第1轮在对所有的边进行松弛后,得到的是从1号顶点只能经过一条边到达其余各定点的最短路径长度。
2轮在对所有的边进行松弛后,得到的是从1号顶点只能经过两条边到达其余各定点的最短路径长度,......
代码待补
---------------- The End ----------------
0%