最短路径问题
- 最短路径：在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径。
1.单源最短路径问题
- 概念：从固定源点出发，求其到所有其他顶点的最短路径
- 无源图的单源最短路径算法(与BFS基本上相似)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
{
Enqueue(S, Q);
while(!IsEmpty(Q))
{
V = Dequeue(Q);
for(V 的每个邻接点W)
{
if(dist[W] = -1) //dist[W] 代表 起点到顶点W的距离
{
dist[W] = dist[V] + 1;
path[W] = V; //path[W] 代表 起点到W经过的顶点，我们一般只存储他的上一个顶点，最小生成树中可以看成其父结点
Enqueue(W, Q);
}
}
}
}
时间复杂度：O(|V| + |T|)
* Dijkstra 算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//伪码描述
void Dijkstra(Vertex s)
{
while(1)
{
V = 未收录顶点中dist最小值; //该算法的时间复杂度取决与这句，如何寻找dist中最小值，dist即distance
if(这样的V不存在)
{
break;
}
collect[V] = true;
for(V的每个邻接点W)
{
if(dist[V] + E<V,W> < dist[W])
{
dist[W] = dist[V] + E<V,W>;
path[W] = V;
}
}
}
}
//Dijkstra算法不能解决有负边的问题。即图中不能存在负值圈（negative-cost cycle）
* 收集dist最小值方法
* 方法1：直接扫描所有未收录的顶点-O(|V|)
由于每次都要扫描，外层循环是|V|次，内层也是，所以总体时间复杂度O(|V|*|V| + |E|) = O(|V|*|V|);|E|是for(V的每个邻接点W)的复杂度
* 方法2：将dist存入最小堆-O(log|V|)
* 更新dist值的复杂度O(log|V|)//这是为什么呢？
* T = O(|V|log|V| + |E|log|V|) = O(|E|log|V|);一般来说边的个数|E|比顶点个数多
* **这里我们可以使用C++ STL里的优先队列来替代自己写最小堆**
2.多源最短路径问题
- 概念：求任意两点的最短路径