基础图论（最短路径）

最短路径问题

一、迪杰斯拉特算法求单源最短路径问题：

1）设A[1…n,1…n]为有向图的带权邻接矩阵，A[i,j]表示弧(Vi,Vj)上的权值，若(Vi,Vj)不存在，则A[i,j]为无穷大；S 为已找到从源点V0出发的最短路径的终点集合，初始状态为{V0}；DIST[1…n]为个终点当前找到的最短路径长度，初始值为DIST[i]=A[V0,i]；

2）选择u，使DIST[u]=min{DIST[w]|w!∈S,w∈V}, S=S∪{u},其中，V为有向图的顶点集合；

3）对于所有不在S中终点w，若 DIST[u]+A[u,w] < DIST[w], 则修改DIST[w]为 DIST[w]=DIST[u]+A[u,w]；

4）重复操作2）、3）共n-1次，由此可求得从V0到各终点的最短路径。

求最短路径步骤:（图例）

1）初始时令 S={V0}, T={其余顶点}，T中顶点对应的距离值

2）若存在<V0,Vi>，为<V0,Vi>弧上的权值

3）若不存在<V0,Vi>，为µ

4）从T中选取一个其距离值为最小的顶点W，加入S

5） 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值

6） 重复上述步骤，直到S中包含所有顶点，即S=V为止

二、弗洛伊德算法：

**1.思想：**逐个顶点试探法

2.步骤：

1）初始时设置一个n阶方阵，令其对角线元素为0，若存在弧<Vi,Vj>，则对应元素为权值；否则为µ。

2）逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值。

3）所有顶点试探完毕，算法结束。

三、迪杰特斯拉算法和弗洛伊德算法的对比：

迪杰特斯拉算法求的是一个顶点到所有顶点的最短路径，但弗洛伊德算法是求所有顶点到所有顶点的最短路径。而弗洛伊德算法非常简洁。