Dijkstra 算法解决带非负权重的有向图上单源路径最短问题，若实现方法合适，则其运行时间小于 Bellman_Ford 算法。
Dijkstra 算法在运行过程中维持一组关键信息：结点集合S，从源节点 s 到该集合中每个结点的最短路径已经被找到。算法将重复从V - S 中选择最短路径估计最小的结点 u，并对它进行加入到集合、对所有从 u 出发的边进行松弛。
其中，我们用最小优先队列管理结点集合 V - S。与之前相同，我们用最短路径估计来作为队列中结点比较的方式。
Dijkstra(G, w, s) Initialize_Single_Source(G, s) S = NULL Q = G.V while Q != NULL u = Extract_Min(Q); S = S∪{u}; for each vertex v∈G.Adj[u] Relax(u, v, w)该算法由源节点出发开始循环，并在循环中一遍又一遍选择d最小的结点，并通过将它出队列中排出，并松弛由它出发的边。因此可以看到，该算法实行的是贪心算法——选取路径最短的结点并纳入到S中。
定理6（Dijkstra 算法的正确性）： Dijkstra 算法运行在带权重的有向图 G = （V， E)时，若所有权重非负，则算法终止时，对于所有结点 v ∈ V，我们有 u.d = δ(s, u)。
证明：
在初始化时，我们有S = NULL，因此直接成立。
在保持的过程中，我们利用反证法进行证明。
我们先假设一个结点 u，它是即将要被划入集合V中的结点。那么利用反证法，那么我们先假设它是第一个加入到集合S时，使得 u.d != δ(s, u)。之后，我们先把这个假设置于一边，通过对从s到u的最短路径的检查来论证 u.d = δ(s, u)。
首先，在初始阶段，源节点 s 被纳入到集合S中时，此时显然 s. d = δ(s, s) = 0，因此它符合结论，u 不可能是它。
那么在之后，我们先考虑不存在从 s 到 u 的路径的情况，此时根据非路径性质，有 u.d = δ(s, u) = ∞，与假设相悖，因此，我们可以得到一个小结论：当结点 u 被纳入到集合S时，一定存在一条从源节点 s 到 u 的最短路径。
那么，我们假设这条路径p =<s, ……, x, y, ……, u>，其中结点 s 到 x 均在集合S内，而 y 到 u 均在集合V-S内。
由于 u 是第一个纳入集合时不符合结论的，那么 x 仍然满足结论，即有 x.d = δ(s, x)，同时，我们根据最优子结构性质和收敛性质，由于 x 被纳入集合时，我们就已经调整边(x, y)，那么我们又得到一个结论：y.d = δ(s, y)。
现在，由于 y 是从 s 到 u 最短路径上的结点，那么我们有y.d = δ(s, y) ≤ δ(s, u) ≤ u.d，其中用到了上界性质，那么我们便得到了一个结论： y.d ≤ u.d，同时，根据算法，我们得到 u.d ≤ y.d（选取d最小的结点），那么我们有 y.d = u.d。
这时，我们再把结论往y.d = δ(s, y) ≤ δ(s, u) ≤ u.d中套，便得到了 δ(s, u) = u.d 的结论。
这与我们的假设不符。
因此即可得证。
在最后，S = V，即可得到所有结点v∈V，均有v.d = δ(s, v)。
好了，严密的理论推导看完了，我们现在来整点阳间的。（说人话）
我们来亲自下海到算法中进行分析。在第一遍循环我们把根结点加入进去，并松弛其周边的结点。这时符合结论。
在第二遍循环时，我们选择集合V - S中 d 最小的结点并把它拉入进去，这时候考虑其是否是最短路径：显然是的！我们若考虑从其他的路径能到达 d 最小的结点的话，很快就会发现问题：从根节点到其他边的本身权值都比 d 大了，又谈何能够选择一条更为短的路径呢？（这建立在边的权值非负的情况下，若可以为负，那就说不定了）
好，前两次循环我们都懂了，接下来我们再继续分析。在第二遍循环中，我们把 d 最小的结点纳入集合S的同时，我们还松弛了由它出发的相邻的边，假设第一个结点为u，然后通过 u 能够到达的结点为从V1 到 Vk，那么Vi.d = δ(s, u) + w(u, Vk) = w(s, u) + w(u, Vk)。其中自然 i 在 1 到 k 之间。
那么在第三遍循环时，我们可以显然的察觉到此时有三种大情况，
1、d 最小的结点位于仅由 s 出发可以到达的边上；
2、d 最小的结点位于仅由 u 出发可以到达的边上；
3、d 最小的结点同时出现在 s 和 u 同时可以到达的边上。
其中第一种情况显然与我们在第二遍循环相同，因此容易证明；
而第二种情况时，看上去多了一条边，出现了很多变数，实际上我们还是那句话：通过源节点 s 到达其他顶点本身所消耗的权值都比 Vi.d 大了，那么何谈你还多出至少一条边使得从其他顶点来到达 Vi 上的权值呢？
对于第三种情况，则会发生一次比较：将第一次循环得到的 Ui. d 的值和u.d +w(u, Ui)进行比较，并选择它们的最小值。可以看到，无论是哪种情况，我们都能把它归纳到情况1或2中的某一种，这时候又变成了我们已知的问题了。
在第四遍循环中可能会出现更多的情况，不过我们再讨论下去已经没有意义了——无论是哪种情况，我们都能把它转换成上述三种大情况中的一种并进行处理。
由此，在第|V|次循环后，我们将得到最终的目的。
推论7：在带权重的有向图G=（V，E）上运行Dijkstra 算法，其中的权重皆为非负，源节点为s，则在算法终止时，前驱子图 Gp是一棵根节点为 s 的最短路径树。
（这个无需证明）
