建立邻接表（邻接矩阵也可以）1
2
3
4
5
6
7
8struct Node
{
int v; //顶点
int dis; //权值
Node(int x, int y): v(x), dis(y){}
};
用vector初始化，即<vector<vector1
2
3
4
5
6
7
8vector<vector<Node>> Adj = {
{Node(0, 0), Node(1, 1), Node(2, INF), Node(3, 4), Node(4, 4), Node(5, INF)},
{Node(0, INF), Node(1, 0), Node(2, INF), Node(3, 2), Node(4, INF), Node(5, INF)},
{Node(0, INF), Node(1, INF), Node(2, 0), Node(3, INF), Node(4, INF), Node(5, 1)},
{Node(0, INF), Node(1, INF), Node(2, 2), Node(3, 0), Node(4, 3), Node(5, INF)},
{Node(0, INF), Node(1, INF), Node(2, INF), Node(3, INF), Node(4, 0), Node(5, 3)},
{Node(0, INF), Node(1, INF), Node(2, INF), Node(3, INF), Node(4, INF), Node(5, 0)}
};
Dijkstra:单源最短路径
采用贪心方法，每次遍历一个点后看经过这个点能不能更短一点
伪代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15X={1}; Y=V-{1}; d[1]=0;
for(y=2 to n)
if y相邻于1 then d[y] = length[1, y]
else d[y]=max(代表无穷)
end if
end for
for j=1 to n-1
令y属于Y，使得d[y]最小
X=X并{y} {将顶点y加入X}
Y=Y并{y} {将顶点y从Y中删除}
for 每条边(y, w)
if w属于Y and 的d[y]+length[y, w]<d[w] then
d[w]=d[y]+length[y, w]
end for
end for
Floyd：各两点的最短路径
简单暴力的搜索
伪代码：1
2
3
4
5
6
7
8D=l {将输入矩阵l复制到D}
for(k=1 to n)
for(i=1 to n)
for(j=1 to n)
D[i][j] = min{D[i][j], D[i][k]+D[k][j]}
end for
end for
end for
完整代码如下：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#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int INF = 65532; //代表无穷大，即不相连
struct Node
{
int v; //顶点
int dis; //权值
Node(int x, int y): v(x), dis(y){}
};
void Dijkstra(int n, int s, vector<vector<Node>> Adj, vector<int> &d, vector<bool> &flag, vector<int> pre)
{
/*
* n：顶点个数
* s：起点
* Adj：图，邻接表
* d[]:到各个顶点的最短路径
* flag[]：标记，有没有访问过
* pre[]: 存储从起点s到达顶点v的最短路径上v的前一个顶点
*/
fill(d.begin(), d.end(), INF); //初始化最短路径矩阵，即出发点离各个顶点为无穷大
d[s] = 0; //出发点离自己的距离为0
for(int i=0; i<n; i++) //初始化
{
pre[i] = i;
}
for(int i=0; i<n; i++)
{
int u = -1; //找到d[u]中最小的u
int MIN = INF; //找到最短路径
for(int j=0; j<n; j++)
{
if(flag[j]==false && d[j] < MIN) //顶点未访问过，贪心找最端的d[u],然后从这顶点开始找
{
u = j;
MIN = d[j];
}
}
//找不到小于INF的d[u]，说明剩下的顶点和起点s不连通
if(u == -1)
{
return;
}
else
{
flag[u] = true;
for(int j=0; j<Adj[u].size(); j++) //从此顶点找最短
{
int v = Adj[u][j].v; //各个顶点
if(flag[v]==false && d[v]>d[u]+Adj[u][j].dis) //若顶点未访问，当前距离比加入的长，替换
{
d[v] = d[u]+Adj[u][j].dis;
}
}
}
}
}
//Floyd算法，暴力求出每两个点的最短路径
void Floyd(int n, int s, vector<vector<Node>> Adj)
{
vector<vector<Node>> D = Adj;
for(int k=0; k<n; k++)
{
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(D[i][j].dis > D[i][k].dis+D[k][j].dis)
{
D[i][j].dis = D[i][k].dis+D[k][j].dis;
}
}
}
}
for(int i=0; i<n; i++)
{
cout << D[0][i].dis << ' ';
}
cout << endl;
}
int main()
{
int n = 6;
vector<vector<Node>> Adj = {
{Node(0, 0), Node(1, 1), Node(2, INF), Node(3, 4), Node(4, 4), Node(5, INF)},
{Node(0, INF), Node(1, 0), Node(2, INF), Node(3, 2), Node(4, INF), Node(5, INF)},
{Node(0, INF), Node(1, INF), Node(2, 0), Node(3, INF), Node(4, INF), Node(5, 1)},
{Node(0, INF), Node(1, INF), Node(2, 2), Node(3, 0), Node(4, 3), Node(5, INF)},
{Node(0, INF), Node(1, INF), Node(2, INF), Node(3, INF), Node(4, 0), Node(5, 3)},
{Node(0, INF), Node(1, INF), Node(2, INF), Node(3, INF), Node(4, INF), Node(5, 0)}
};
vector<bool> flag(n);
vector<int> d(n);
vector<int> pre(n);
Dijkstra(n, 0, Adj, d, flag, pre);
for(int i=0; i<n; i++)
{
cout << d[i] << ' ';
}
cout << endl;
Floyd(n, 0, Adj);
//cout << flag[0] << ' ' << d[0] << ' ' << pre[0] << endl; 输出为0 0 0
//cout << Adj[3][0].v << endl; //输出为3
cout << "Hello world" << endl;
return 0;
}
