佛洛伊德算法時(shí)間復(fù)雜度為O(n^3)，其中n為頂點(diǎn)的個(gè)數(shù)。

Floyd可求出任何一對(duì)頂點(diǎn)之間的最短路徑。允許圖中有帶負(fù)權(quán)值的邊，但是不允許有包含帶負(fù)權(quán)值的邊組成的回路。

#include <iostream> using namespace std;#define Maxsize 100 typedef char VertexType; typedef int EdgeType;typedef struct{VertexType Vex[Maxsize];EdgeType edge[Maxsize][Maxsize];int vexnum,arcnum; }MGraph;void Floyd(MGraph G,int A[][Maxsize],int path[][Maxsize]){int i,j,k;for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++){A[i][j]=G.edge[i][j]; //初始化path[i][j]=-1; }for(k=0;k<G.vexnum;k++) //經(jīng)過(guò)k頂點(diǎn) for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++) //i->j的距離if(A[i][j]>A[i][k]+A[k][j]){A[i][j]=A[i][k]+A[k][j];path[i][j]=k;} }

?

總結(jié)

以上是生活随笔為你收集整理的最短路径-Floyd（佛洛伊德算法）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。