有关最短路的一切

登录以参加训练计划

最短路

定义

最短路问题就是求出两点之间的最短路径。基于给定的图的性质不同，需要采取不同的方法来求出这条最短路。

以下是剧透别看，请先用最朴素、直觉的方式去思考，三个例题的图都有什么性质，可以设计什么样的算法？

无权最短路 - BFS

有权最短路 - Dijkstra

含负权的最短路 - Bellman–Ford

题目都分析完了，那么我们来看几个处理最短路问题的经典算法。

无权最短路 - BFS

用queue + while循环，按层由浅到深访问，第一次找到目标节点就是最短路。

无敌最短路 - Floyd

dist[k][i][j] 表示只看前k个点的情况下，i到j的最短路距离。

显然

for (int k = 1; k <= n; k++)
  for(int i = 1; i <= n; i++) 
    for (int j = 1; j <= n; j++)
      // 要么k节点对最短路没有影响、要么经过k可以找到一条新的最短路
      dist[k][i][j] = min(dist[k-1][i][j], 
      dist[k-1][i][k] + dist[k-1][k][j]) 

dist[0][i][j] 初始化

• 在(i,j)有边的情况下就是边权，
• 没有的话就是0x3f3f3f3f。

额外说一句

这像不像0/1背包的思路，value[k][w] 就是在我只看前k个包的时候，w重量的最大价值；而转移公式就是

value[k][w] = max(value[k-1][w], value[k-1][w-W[k]] + val[k])

然后还能像背包一样把第一维去掉。

for (int k = 1; k <= n; k++)
  for(int i = 1; i <= n; i++) 
    for (int j = 1; j <= n; j++)
      dist[i][j] = min(dist[i][j], 
      dist[i][k] + dist[k][j])

有权最短路 - Dijkstra

Dijkstra在就是小奥的标数法。把节点分成访问过 / 没访问过 两个集合。每次：

1. 找到没访问过里面距离最小的$node_i$，标记为访问过的，当前的距离就是最近距离
2. 利用$node_i$去更新所有未访问节点的距离

如果含有负权边，就完蛋了。（想一下为什么？）

利用priority_queue<int, vector<int>, greater<int>>最小堆来管理未访问的集合，可以取得更高的O(N)的优化 （ 这东西找最小O(1)，每次push一个新元素O(logn) )

含负权的最短路 - Bellman–Ford