场景
- 给定带权网络G,远点s 对于所有的其他顶点v, s到v的最短通路是多少?该通路由哪些边构成
性质
- 单调性
- 最短路径树上的任一顶点v到必定是源点s到v的最短路径
- 歧义性
- 无环性
和最小支撑树的区别
- 最小支撑树求的是整个拓扑图的所有路径之和最小,不能保证任意两点之间的路径最小应用场景: 快递车将霍送到城市的每一个快递点,不走重复的路而且时间最短
- 最短路径是保证源点到任一一点的路径最短应用场景: 地图寻径,怎么确保可以最短时间到达想要去的地方
代码实现
// 最短路径算法
template <typename Tv, typename Te> struct DijkstraPU{
// 重载()
virtual void operator()(Graph<Tv, Te>* graph, int v int u) {
// 针对未发现邻接顶点
if (graph->status(u) != UNDISCOVER) {
return;
}
// 因为只针对两点之间最短,所以此处和父级优先级树和边权重之和比较
if (graph->priority(u) > graph->priority(v) + graph->weight(v, u)) {
graph->priority(u) = graph->priority(v) + graph->weight(v, u)
graph->parent(u) = v;
}
}
};
// 优先级搜索算法
template <typename PU> void pfs(int v, PU prioUpdater){
// 重置图状态
reset();
// 时间标签
int clock = 0;
int s = v;
// 遍历所有顶点
do {
// 所有未发现的顶点执行优先级搜索算法
if (status(v) == UNDISCOVERED) {
PFS(v, prioUpdater);
}
// 迭代到下一顶点
v = ++v%n;
} while (s != v);
}
// 连通域 优先级搜索框架
template <typename PU> void PFS(int v, PU prioUpdater) {
// 更新顶点优先级,状态
priority(v) = 0; // 最高优先级
status(v) = VISITED;
// 起点s加入遍历树中
parent(s) = -1;
// 遍历所有顶点
while(true) {
// 更新当前顶点的邻接顶点的优先级数和父级顶点
for (int w = firstNbr(s); w > -1 ; w = nextNbr(s, w)) {
prioUpdater(this,s, w);
}
// 获取尚未加入遍历树中的所有顶点中优先级数最小的顶点
int shortest = INT_MAX;
for (int w =0; w < n ; w++) {
if (status(w) == UNDISCOVERED && priority(w) < shortest) {
shortest = priority(w);
s = w;
}
}
// TODO 自定义一些事情
// 所有顶点都已经遍历过了
if (status(s) == VISITED) {
break;
}
// 更新当前顶点的状态
status(s) = VISITED;
type(parent(s), s) = TREE;
}
}