无权图单源最短路径
无权图单源最短路径
.png
维护2个数组：
dist[w]，表示v到w的权值之和(初始时，dist[s] = 0，其余都为-1，s源点)
parent[w]，表示v到w的路线中w的父节点。(按这个遍历上去，就可以得到v到w的最短路径的路线)
void Unweighted(Vertex S)
{
queue.EnQueue(S);
while(!queue.IsEmpty()) {
V = queue.DeQueue();
for (V 的每一个邻接点 W) {
if (dist[W] == -1) {
dist[W] = dist[V] + 1;
parent[W] = V;
queue.EnQueue(W);
}
}
}
}
有权图单源最短路径
a.png
有权图单源最短路径和无权图最短路径不一样，不能单从节点数来看，比如上图中，V1到V6，节点最少的路线是V1->V4->V6。但这并不是权值最小的。
Dijkstra算法
维护2个数组：
dist[w]，表示 v 到 w 的权值之和(初始时，dist[s] = 0，其余都为∞，s源点)
path[w]，表示 v 到 w 的路线中w的父节点。(按这个遍历上去，就可以得到v到w的最短路径的路线)
void Dijkstra(Vertex s)
{
while(true) {
V = 未收录顶点中dist最小值者。
if (没有这样的顶点)
break;
collected[V] = true;
for (V 的每一个邻接点W) {
if (collected[W] == false) {
dist[w] = dist[v] + E<V, W>
path[w] = V;
}
}
}
}
Dijkstra算法过程.png
