最小路径算法（Dijkstra算法和Floyd算法）

1.单源点的最短路径问题：给定带权有向图G和源点v，求从v到G中其余各顶点的最短路径。

我们用一个例子来具体说明迪杰斯特拉算法的流程。

定义源点为 0，dist[i]为源点 0 到顶点 i 的最短路径。其过程描述如下：

步骤dist[1]dist[2]dist[3]dist[4]已找到的集合
第 1 步   8   1   2   +∞   {2}  
第 2 步   8   ×   2   4   {2, 3}  
第 3 步   5   ×   ×   4   {2, 3, 4}  
第 4 步   5   ×   ×   ×   {2, 3, 4, 1}  
第 5 步   ×   ×   ×   ×   {2, 3, 4, 1}