最短路
单源最短路：分为：
1、所有边权都是正数；n是点数，m是边数，两个算法：朴素Dijkstra算法$O(n^2)$、堆优化版Dijkstra算法$O(mlogn)$ 。
2、存在负权边；两个算法：Bellman-Ford $O(nm)$、 SPFA 一般情况：$O(m)$、最坏$O(nm)$.
- 多源汇最短路：Floyd算法：$O(n^3)$。
- 稠密图的存储：邻接矩阵；稀疏图的存储：邻接表。
朴素Dijkstra算法
流程：
1
2
3
4
5-初始化： dist[1] = 0， dist[i] = 正无穷，s为当前已确定最短距离的点；
- for v in 1~n：
t<---不在s中的，距离最近的点；
add t to s;
用t更新其他点的距离
1 | /* |
python：
1 | def dijkstra(): |
堆优化版Dijkstra算法
适合用于稀疏图
堆的实现：手写堆、优先队列（可能存储冗余点）。
流程：
1
2
3
4
5-初始化： dist[1] = 0， dist[i] = 正无穷，s为当前已确定最短距离的点；
- for v in 1~n：
t<---不在s中的，距离最近的点；[利用堆来找：O(1)]
add t to s;
用t更新其他点的距离 [堆上做更新：O(mlgn)，m是边的数目]
c++：
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
using namespace std;
const int N = 100010;
bool st[N];
int dist[N];
int h[N], e[N], w[N], ne[N], idx;
typedef pair<int,int> PII;
int n, m;
void add(int x, int y, int z)
{
e[idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx ++;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); //距离与节点编号
while(heap.size())
{
auto mi = heap.top();
heap.pop();
int idx = mi.second, distance = mi.first;
if(st[idx]) continue;
st[idx] = true;
for(int j = h[idx]; j != -1; j = ne[j])
{
int jv = e[j];
if(dist[jv] > w[j] + distance)
{
dist[jv] = w[j] + distance;
heap.push({dist[jv], jv});
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d",&n, &m);
for(int i = 1; i <= m; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
}
printf("%d\n", dijkstra());
return 0;
}
python：
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/*
堆优化Dijkstra:存储方式改为邻接表
*/
from queue import PriorityQueue
class LinkedTable:
def __init__(self, n, m):
self.h = [-1] * (n + 1)
self.e = [0] * (m + 1)
self.w = [float('inf')] * (m + 1)
self.ne = [0] * (m + 1)
self.idx = 0
def adds(self, start, end, weight):
"""
e[idx]:边idx的起点
ne[idx]:与边idx有相同起点的其他边的other_idx
w[idx]:边idx的权重
h[x]:节点x开始的链表头部
"""
self.e[self.idx] = end
self.w[self.idx] = weight
self.ne[self.idx] = self.h[start]
self.h[start] = self.idx
self.idx += 1
def dijkstra():
q = PriorityQueue()
q.put((0, 1)) # 距离、编号
dist[1] = 0
while not q.empty():
distance, pos = q.get()
if st[pos]: continue
st[pos] = True
j = g.h[pos]
while j != -1:
w = g.w[j]
startNode = g.e[j]
if dist[startNode] > distance + w:
dist[startNode] = distance + w
q.put((dist[startNode], startNode))
j = g.ne[j]
if dist[n] == float('inf'): return -1
return dist[n]
if __name__ == "__main__":
n, m = map(int, input().split())
g = LinkedTable(n, m)
dist = [float("inf")] * (n + 1)
st = [False] * (n + 1)
for _ in range(m):
x, y, z = map(int, input().split())
g.adds(x, y, z)
print("%s" % dijkstra())
- 理解一个算法没有任何意义，必须多写！！！！！
Bellman-Ford算法
流程：时间复杂度 $O(nm)$.
1
2
3
4
5
6
7for n（节点数目）次: 【意义：迭代k次，代表从1号点，经过不超过k条边的最短路的距离；当第n次迭代做更新时，说明存在一条长度是n的最短路径，意味着n + 1号点，但只有n个点，所以存在一个负环】
备份：防止更新结果串联
for 所有边 a,b,w: a------>b :权重为w
dist[b] = min(dist[b], dist[a] + w)
for结束后所有边都满足：
dist[b] <= dist[a] + w有负权回路的情况下,不一定存在最短回路。
backup：某一个点A到B的距离已经在第二个for循环内更新，之后松弛的边可能会比较已经更新的距离，因此应该用之前更新的距离来做。
1 | /* |
1 | import copy |
SPFA
路程：
1
2
3
4
5
6queue <--- 1:
while queue 非空：
t <--- q.front
q.pop();
更新t的所有出边：t--->b
queue <--- b1
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/*
利用队列做优化：队列存的是节点距离变小的点的编号，
st[i]:对于已经使用过的点记录不再使用；
图的存储为数组模拟的邻接表；
st数组去掉之后不影响算法正确性，但队列中会存储重复元素，效率会下降。
spfa只会更新所有能从起点走到的点，所以如果无解，那么起点就走不到终点，那么终点的距离就是0x3f3f3f3f
*/
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], w[N], ne[N], idx;
bool st[N];
int dist[N];
void add(int x, int y, int z)
{
e[idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx ++;
}
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while(q.size())
{
int node = q.front();
q.pop();
st[node] = false; //因为存在负环
for(int i = h[node]; i != -1; i = ne[i])
{
int ver = e[i];
if(dist[ver] > dist[node] + w[i])
{
dist[ver] = dist[node] + w[i];
if (!st[ver])
{
q.push(ver);
st[ver] = true;
}
}
}
}
return dist[n];
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
}
int res = spfa();
if (res == 0x3f3f3f3f) puts("impossible");
else printf("%d", res);
return 0;
}python:
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
54class LinkedTable:
def __init__(self, n, m):
self.h = [-1] * (n + 1)
self.e = [0] * (m + 1)
self.w = [float('inf')] * (m + 1)
self.ne = [0] * (m + 1)
self.idx = 0
def adds(self, start, end, weight):
"""
e[idx]:边idx的起点
ne[idx]:与边idx有相同起点的其他边的other_idx
w[idx]:边idx的权重
h[x]:节点x开始的链表头部
"""
self.e[self.idx] = end
self.w[self.idx] = weight
self.ne[self.idx] = self.h[start]
self.h[start] = self.idx
self.idx += 1
def spfa(s):
q = [s]
dist[s] = 0
st[s] = True
while len(q) > 0:
idx = q.pop(0)
st[idx] = False
j = g.h[idx]
while j != -1:
endNode = g.e[j]
weight = g.w[j]
if dist[endNode] > dist[idx] + weight:
dist[endNode] = dist[idx] + weight
st[idx] = True
q.append(endNode)
j = g.ne[j]
return dist[n]
if __name__ == "__main__":
n, m = map(int, input().split())
g = LinkedTable(n, m)
dist = [float('inf')] * ( n + 1 )
st = [False] * (n + 1)
for _ in range(m):
x, y, z = map(int, input().split())
g.adds(x, y, z)
res = spfa(1)
if res == float('inf'): print("impossible")
else: print(res)
求负环：思路与bellman-ford一样
1
2
3
4
5
6
7dist[x]:当前从1号点到n号点的最短距离；
cnt[x]:当前最短路上的边数；
当cnt[x]>=n时，表示图中存在负环。
更新：
dist[x] = dist[t] + w[i];
cnt[x] = cnt[t] + 1;
floyd
流程：
1
2
3
4
5
6
7
8
9
10
11d[k, i, j]:表示从i这个点，只经过1~k这些中间点，到达j的最短距离。从
d[k, i, j] = d[k-1, i, k] + d[k-1, k, j]
d[i, j] = d[i, k] + d[k, j]
d[i,j]:邻接矩阵
for (k =1; k <=n; k++)
for (i = 1; i <=n; i++)
for( j = 1; j <=n; j++)
d[i,j] = min(d[i,j] d[i,k] + d[k, j])
循环结束后：d[i,j]存的就是从i到j的最短距离
c++：
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
using namespace std;
const int N = 210,INF = 1e9;
int g[N][N];
int n, m, k;
void floyd()
{
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
if (i == j) g[i][j] = 0;
else g[i][j] = INF;
for(int i = 0; i < m; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
g[x][y] = min(g[x][y], z);
}
floyd();
while( k -- )
{
int x, y;
scanf("%d%d", &x, &y);
if(g[x][y] > INF / 2) puts("impossible");
else printf("%d\n", g[x][y]);
}
return 0;
}
python：
1 | def floyd(): |
- 思路比模拟更重要，特别是动态规划问题。
最小生成树
- 朴素版prim—稠密图：$O(n^2)$
- 堆优化版prim—稀疏图：$O(mlogn)$
- Kruskal—-稀疏图：$O(mlogm)$
prim流程：
1
2
3
4
5dist[i] 初始为正无穷 //dist表示点i到集合的距离
for(i=0; i < n; i++) //选择加入n个点
t <--- 找到集合外距离最近的点
用t更新其他点到集合（Dijkstra是更新到源点的距离）的距离
st[t] = true
集合：当前已经在联通块中的所有点。
到集合的距离：也就是点有多条边连接到该集合，最小的那条边便是点到该集合的距离。
生成树：选择t的时候连接的边。
1 |
|
kruskal算法流程：
1
2
31.将所有边权权重从小到大排序；//O(mlogm)
2.从小到大枚举每条边ab，权重是c；
if ab不连通，将ab加入集合中；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
using namespace std;
const int M = 200010, N = 100010, INF = 0x3f3f3f3f;
int n, m;
int p[N];
struct Edge{
int u, v, w;
bool operator < (const Edge &T) const
{
return w < T.w;
}
}edge[M];
int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int kruskal()
{
for(int i = 1; i <= n; i++) p[i] = i;
sort(edge, edge + m);
int res = 0, cnt = 0;
for(int i = 0; i < m; i++)
{
int u = edge[i].u, v = edge[i].v, w = edge[i].w;
int pu = find(u), pv = find(v);
if(pu != pv)
{
p[pu] = pv; //根节点的父节点=另一个节点的父节点
res += w;
cnt ++;
}
}
if (cnt >= n - 1) return res;
return INF;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
edge[i] = {u, v, w};
}
int res = kruskal();
if(res == INF) puts("impossible");
else printf("%d\n", res);
return 0;
}
二分图
- 染色法：$O(n + m)$
- 匈牙利法：$O(nm)$实际运行时间远小于。
二分图：把所有的点划分成两个集合，集合内部没有边。 设$G=(V,E)$是一个无向图，如果顶点$V$可分割为两个互不相交的子集(A,B)，并且图中的每条边$（i，j）$所关联的两个顶点$i$和$j$分别属于这两个不同的顶点集(i in A,j in B)，则称图$G$为一个二分图。
二分图一定是连通图嘛? 只要能将所有点分成两个集合，使得所有边只出现在集合之间，就是二分图。
一个图是二分图当且仅当图中不含奇数环（环当中边的数量是奇数）。
- 染色法：深度优先遍历的方式对每一个节点染色，使得连接边的两个点的颜色不一致，若出现矛盾则返回false.
1 | 流程： |
1 |
|
- 匈牙利法：最坏情况下：时间复杂度 $O(nm)$，即每个点最坏情况下会遍历所有的边。
枚举左边的点集，那么存储的边是左边指向右边就行，因为枚举左边点时，只会找左边的点能够指向的边；
match数组：右边的点对应的点；st数组：右边点是否已经考虑过。匹配结果记录在match中，st数组用来判重，避免在某次匹配中重复遍历点和边。
st数组用来防止重复搜索相同的点。当图中有环的时候，不加st数组可能会无限循环下去，就出现段错误了。
1 |
|
邻接矩阵版：
1 |
|