两种常见的最短路径问题：
一、单源最短路径–用Dijistra迪杰斯特拉）算法
二、所有顶点间的最短路径–用Floyd（弗洛伊德）算法
Dijistra算法
1、初始化：先找出从源点v0到各终点Vk的的直达路径(V0, Vk)，即通过一条弧直达的路径。
2、选择：从这些路径中找出一条长度最短的路径(V0, U)。
3、更新：然后对其余各路径进行适当调整：
若在图中存在弧(U, Vk)，且(V0, U) + (U, Vk) < (V0, Vk)，则以路径(V0, U, Vk)代替(V0, Vk)。
在调整的各条路径中，再找到长度最短的路径，依此类推
迪杰斯特拉（Dijkstra）算法：按路径长度递增次序产生最短路径
1、把V分成两组：
（1）S：已求出最短路径的顶点的集合。
（2）T = V - S：尚未确定最短路径的顶点集合。
2、将T中顶点按最短路径递增的次序加入到S中，
保证：（1）从源点v0到S中各项点的最短路径长度都不大于从v0到T中任何顶点的最短路径长度。
（2）每个顶点对应一个距离值：
S中顶点：从v0到此顶点的最短路径长度
T中顶点：从v0到此顶点的只包括S中顶点作中间顶点的最短路径长度
**Dijkstra算法步骤：**初始时令 S = {v0}, T = {其余顶点}。
T中选取一个其距离值最小的顶点vj，加入S。对T中顶点的距离值进行修改：若加进vj作中间顶点，从v0到vi的距离值比不加vj的路径相加，则修改此距离值。
加入v2顶点之后
加入顶点v1之后
!
依此类推，直到S = V
Floyd算法
算法思想：逐个试探，从vi到vj的所有可能存在的路径中，选出一条长度最短的路径
求最短路径步骤：初始时设置一个n阶矩阵方针，令其对角线元素为0，若存在弧<Vi, Vj>，则其对应元素为权值；否则为∞。逐步试着在原直接路径中增加中间顶点，若加入中间顶点后路径变短，则修改；否则维持原值。所有顶点试探完毕，算法结束。
