多源最短路径Floyd算法

设d[i][j]为顶点 i 与顶点 j 的最短路径，设 k为i与j之间的点，那么d[i][j] = d[i][k] + d[k][j];

算法核心为：

void floyd()
{
    int i,j,k;
    for(k = 1; k <= n; k++)
    {
        for(i = 1; i <= n; i++)
        {
            for(j = 1; j <= n; j++)
            {
                if(d[i][k] + d[k][j] < d[i][j])
                {
                    d[i][j] = d[i][k] + d[k][j];
                    path[i][j] = k;
                }    
            }                
        }    
    }   
}

path[i][j]记录的是最短路径中到j的上一个点，初始化为-1，若最后path[i][j] = -1,说明j是与源点i相邻的点

例：

#include<iostream>
#include<vector>
#include<windows.h>
using namespace std;
#define NUM 101
#define INF 99999999 
int d[NUM][NUM];
int path[NUM][NUM];
int n,m;
void floyd()
{
    int i,j,k;
    for(k = 1; k <= n; k++)
    {
        for(i = 1; i <= n; i++)
        {
            for(j = 1; j <= n; j++)
            {
                if(d[i][k] + d[k][j] < d[i][j])
                {
                    d[i][j] = d[i][k] + d[k][j];
                    path[i][j] = k;
                }    
            }                
        }    
    }   
}

void findPre(int i,int j)
{
	cout<<j<<"-";
    if(path[i][j] == -1)
    {
        cout<<i;
		return;
    }    
     else
     {
		 findPre(i,path[i][j]);
     }  
}
int main()
{
    int i,j;
    scanf("%d%d",&n,&m);
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= n; j++)
        {
            d[i][j] = INF;
            path[i][j] = -1;    
        }    
    }
    for(i = 1; i <= m; i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        d[a][b] = d[b][a] = c;    
    }
    floyd();
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= n; j++)
        {
            if(d[i][j] < INF && i == 1 && j != 1)
            {
                printf("%d到%d的最短路径为：%d ",i,j,d[i][j]);
                printf("路径为：");
                findPre(i,j);
				printf("\n");
            } 
        }
    }
    system("pause");
    return 0;
        
}