Dijkstra
最短路径问题 : 给定一个带权有向图 G = (V, E, W)，同时给定一个源点 u (u ∈ V)，我们要找出从源点 u 出发到其它各点的最短路径距离，并得出这些最短路径的具体路径有哪些边构成。
其实我们要求的就是从 源点 u 出发到 其它各点 str的最短路径所组成的路线网络，也就是一个 最短路径树。
最短路径问题 : 给定一个带权有向图 G = (V, E, W)，同时给定一个源点 u (u ∈ V)，我们要找出从源点 u 出发到其它各点的最短路径距离，并得出这些最短路径的具体路径有哪些边构成。
我们以下面这个带权有向图为示例
我们若以 A 为源点，得到如下的最短路径
我们可以把源点到各点最短路径用绿色标记一下
我们可以看出所有的最短路径构成了一个最短路径树
我们要求的从 源点 到 其它各点 的最短路径所组成的路线网络，就是这个最短路径树。
在上面的图中，我们不难发现，当我们确定了源点 u 到某个其它的点 v 的最短路径时，在这个最短路径的具体路线中，若有一个中转点 t，那么在这个最短路径中从源点 u 到 t 的路径也一定是 u 到 t 的最短路径(之一)。也就是说，假设源点 u 到 v 的最短路径为 p，那么p任意的前缀路径 q 一定是最优的(最短路径之一)。如果 q 不是最优的，那么就会存在另一个更短的路径比 p 更短。
这个性质还是很重要的，是解决单源最短路径问题的核心
我们画个图来理解一下
歧义性
在上面的阐述中也稍微提到一点，就是最短路径其实不一定是唯一的，有可能存在两个路径，它们的路径距离一样且都是最短的，那么此时我们二选其一就可以啦。还有一个问题就是，我们的边权都应当是正数，如果边权存在非正数，那么我们是无法定义这个图中的最短路径的(距离确实不能是非正数呀，除了自己到自己
标签：路径,dist,int,源点,算法,最短,Dijkstra,顶点,贪心 From： https://www.cnblogs.com/galaxyStar/p/17018385.html