本文主要是介绍【图论】最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Floyed算法
【思想】Floyed-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来 得到最佳路径。 注意单 独一条边的路径也不一定是最佳路径。
从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。
对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
时间复杂度O(n^3),只要有存下邻接矩阵的空间，时间一般没问题，并且不必担心负权边的问题。
【实现】
for (i=1;i<=n;i++) for (j=1;j<=n;j++) map[i][j]=INF;for (i=1;i<=n;i++) {scanf("%d%d%d",&peo[i],&a,&b);map[i][a]=1; map[a][i]=1;map[i][b]=1; map[b][i]=1;}for (k=1;k<=n;k++)for (i=1;i<=n;i++)for (j=1;j<=n;j++) if (i!=j && j!=k && i!=k)if (map[i][j]>map[i][k]+map[k][j])map[i][j]=map[i][k]+map[k][j];
for k:=1 to n dofor i:=1 to n dofor j:=1 to n doif （a[i,k]=1）and (a[k,j]=1) then a[i,j]=1
{a[i,j]=1表示i可达j，a[i,j]=0表示i不可达j}这篇关于【图论】最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
