一、最短路径问题的抽象
在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径
这条路径就是两点之间的最短路径（ShortestPath）
第一个顶点为源点（Source）
最后一个顶点为终点（Destination）
二、问题分类
单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径
有向无权图
有向有权图
多源最短路径问题：求任意两顶点间的最短路径
三、无权图的单源最短路算法按照递增（非递减）的顺序找出到各个顶点的最短路
四、有权图的最短路算法
单源：Dijkstra算法
多源：Floyd算法
1、Dijkstra算法
令S={源点s+已经确定了最短路径的顶点vi}
对任一未收录的顶点v，定义dist[v]为s到v的最短路径长度，但该路径仅经过S中的顶点。即路径{s-(viinS)-v}的最小长度
若路径是按照递增（非递减）的顺序生成的，则
真正的最短路必须只经过S中的顶点
每次从未收录的顶点中选一个dist最小的收录（贪心）
增加一个v进入S，可能影响另外一个w的dist值！
dist[w]=min{dist[w],dist[v]+v,w的权重}
方法1：直接扫描所有未收录顶点–O(
V
)
T=O(
V
^2+
E
)
方法2：将dist存在最小堆中–O(log
V
)
更新dist[w]的值–O(log
V
)
T=O(
V
log
V
+
E
log
V
)=O(
E
log
V
)
2、Floyd算法
D[j]=路径{i-{l=k}-j}的最小长度
D0,D1,…,D
V
-1[j]即给出了i到j的真正最短距离
最初的D-1是什么？
当Dk-1已经完成，递推到Dk时：
或者k不属于最短路径{i-{l=k}-j}，则Dk=Dk-1
或者k属于最短路径{i-{l=k}-j}，则该路径必定由两段最短路径组成：Dk[j]=Dk-1[k]+Dk-1[k][j]
预览时标签不可点收录于话题#个上一篇下一篇