弗洛伊德算法

水深无声 2024-02-17 15:04 64阅读 0赞

### 弗洛伊德算法详解 ###

**算法的数据结构**

弗洛伊德算法采用图的带权邻接矩阵存储结构。

**算法基本思想**

假设求顶点Vi到Vj的最短路径。弗洛伊德算法依次找从Vi到Vj，中间经过结点序号不大于0的最短路径，不大于1的最短路径，…直到中间顶点序号不大于n-1的最短路径，从中选取最小值，即为Vi到Vj的最短路径。

**算法具体描述**

若从Vi到Vj有弧，则从Vi到Vj存在一条长度为弧上权值（arcs\[i\]\[j\] ）的路径，该路径不一定是最短路径，尚需进行n次试探。  
首先考虑从Vi到Vj经过中间顶点V0的路径（Vi，V0，Vj）是否存在，也就是判断弧（Vi，V0）和（V0，Vj）是否存在。若存在，则比较（Vi，Vj）和（Vi，V0，Vj）的路径长度取较短的为从Vi到Vj的中间顶点序号不大于0的最短路径。  
在此路径上再增加一个顶点V1，也就是说，如果（Vi，…V1）和（V1，…Vj）分别是当前找到的中间顶点序号不大于0的最短路径，那么，（Vi，…V1，…Vj）就有可能是从Vi到Vj的中间顶点序号不大于1的最短路径。将它和已经得到的从Vi到Vj中间顶点序号不大于0的最短路径相比较，从中选出最短的作为从Vi到Vj中间顶点序号不大于1的最短路径。  
然后，再增加一个顶点V2继续进行这个试探过程。  
一般情况下，若（Vi，…Vk）和（Vk，…Vj）分别是从Vi到Vk和从Vk到Vj的中间顶点序号不大于k-1的最短路径，则将（Vi，…，Vk，…Vj）和已经得到的从Vi到Vj的中间顶点序号不大于k-1的最短路径相比较，其长度最短者即为从Vi到Vj的中间顶点序号不大于k的最短路径。  
经过n次比较之后，最后求得的便是从Vi到Vj的最短路径。  
按此方法可同时求得各对顶点之间的最短路径。  
现定义一个n阶方阵序列  
D（-1），D（0），D（1），…，D（k），…，D（n-1）  
其中  
D（-1）\[i\]\[j\]=arcs\[i\]\[j\]  
D（k）\[i\]\[j\]=Min\{ D（k-1）\[i\]\[j\], D（k-1）\[i\]\[k\]+D（k-1）\[k\]\[j\]\}0≤k≤n-1  
上述公式中，D（1）\[i\]\[j\]是从 Vi到Vj的中间顶点序号不大于 k的最短路径长度；D（n-1）\[i\]\[j\]是从Vi到Vj的最短路径长度。

**算法实现**

void shortestpath\_Floyd(MgraphG,pathmatrix &P\[\],Distancmatrix &D)\{

//用Floyd算法求有向网G中各对顶点v和w之间的最短路径P\[v\]\[w\]及其带权路径长度D\[v\]\[w\]。  
//若P\[v\]\[w\]\[u\]为TRUE，则u是从v到w当前求得最短路径上的顶点。  
For (v=0;v<G.vexnum;++v)//各对顶点之间路径和距离初始化  
For (w=0;w<G.vexnum;++w)\{  
D\[v\]\[w\]=G.arcs\[v\]\[w\];  
For (u=0;u<G.vexnum;++u)P\[v\]\[w\]\[u\]=false;  
If (D\[v\]\[w\]<INFINITY)\{//从v到w有直接路径  
P\[v\]\[w\]\[v\]=true;P\[v\]\[w\]\[w\]=true;  
\}//if  
\}//for  
for (u=0;u<G.vexnum;++u)  
for (v=0;v<G.vexnum;++v)  
for (w=0;w<G.vexnum;++w)  
if (D\[v\]\[u\]+D\[u\]\[w\]<D\[v\]\[w\])\{//从v经u到w的一条路径更短  
D\[v\]\[w\]= D\[v\]\[u\]+D\[u\]\[w\]；  
For (I=0;I<G.vexnum;++I)  
P\[v\]\[w\]\[I\]=P\[v\]\[u\]\[I\]|| P\[u\]\[w\]\[I\];  
\}//if  
\}//shortestpath\_Floyd