#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
typedef struct SHORTRSTPATH_STRU
{
    int size;//图中节点的个数
    int**pathLen;//二位数组保存每对顶点中的最短路径长度
    int **nextVex;//二维数组保存vi到vj最短路径上vi后续节点的下标
}ShortPath;
typedef struct GRAPHMATRIX_STRU
{
    int size;
    int **graph;
}GraphMatrix;

GraphMatrix* InitGraph(int num)
{
    int i,j;
    GraphMatrix *graphMatrix=(GraphMatrix*)malloc(sizeof(GraphMatrix));
    graphMatrix->size=num;
    graphMatrix->graph=(int**)malloc(sizeof(int*)*graphMatrix->size);
    for(i=0;i<graphMatrix->size;i++)
        graphMatrix->graph[i]=(int*)malloc(sizeof(int)*graphMatrix->size);
    for(i=0;i<graphMatrix->size;i++)
    {
        for(j=0;j<graphMatrix->size;j++)
        graphMatrix->graph[i][j]=MAX;

    }
    return graphMatrix;
}
void ReadMatrix(GraphMatrix*graphMatrix)
{
    int vex1,vex2,weight;
    scanf("%d%d%d",&vex1,&vex2,&weight);
    while(vex1!=0||vex2!=0)
    {
        graphMatrix->graph[vex1][vex2]=weight;
        scanf("%d%d%d",&vex1,&vex2,&weight);
    }

}

ShortPath*floyd(GraphMatrix*graphMatrix)
{
    int i,j,vex;
    ShortPath *shortPath=NULL;
    shortPath=(ShortPath*)malloc(sizeof(ShortPath));
    shortPath->size=graphMatrix->size;
    //分配空间二维数组
    shortPath->nextVex=(int**)malloc(sizeof(int*)*shortPath->size);
    for(i=0;i<shortPath->size;i++)
    shortPath->nextVex[i]=(int*)malloc(sizeof(int)*shortPath->size);
    //分配空间二维数组
    shortPath->pathLen=(int**)malloc(sizeof(int*)*shortPath->size);
    for(i=0;i<shortPath->size;i++)
        shortPath->pathLen[i]=(int*)malloc(sizeof(int)*shortPath->size);
    //初始化
    for(i=0;i<shortPath->size;i++)
    {
        for(j=0;j<shortPath->size;j++)
        {   
            //为了不破坏图的原有结构，使用辅助数组进行数据的迭代
            shortPath->pathLen[i][j]=graphMatrix->graph[i][j];
            if(shortPath->pathLen[i][j]==MAX)
                shortPath->nextVex[i][j]=-1;
            else
                shortPath->nextVex[i][j]=j;
        }
    }
    //正式开始计算
    for(vex=0;vex<graphMatrix->size;vex++)
    {
        for(i=0;i<graphMatrix->size;i++)
        {
            for(j=0;j<graphMatrix->size;j++)
            {
                if(shortPath->pathLen[i][vex]==MAX||shortPath->pathLen[vex][j]==MAX)
                    continue;
                    //路径更短，则更新
                if(shortPath->pathLen[i][vex]+shortPath->pathLen[vex][j]<shortPath->pathLen[i][j])
                {
                    shortPath->pathLen[i][j]=shortPath->pathLen[i][vex]+shortPath->pathLen[vex][j];
                    shortPath->nextVex[i][j]=shortPath->nextVex[i][vex];
                }
            }
        }

    }
    return shortPath;
}
int main()
{  
    //最短路径测试
   GraphMatrix*graphMatrix=NULL;
   ShortPath*shortPath=NULL;
   int i,j,k,e,maxdistan[6],min=0;
   graphMatrix=InitGraph(6);
   ReadMatrix(graphMatrix);//读图
   shortPath=floyd(graphMatrix);//使用floyd算法
   for(i=0;i<graphMatrix->size;i++)
   {   
       
       for(j=0;j<graphMatrix->size;j++)
       {
           if(i!=j&&shortPath->pathLen[i][j]!=MAX)
           {
               printf("从%d到%d的最短路径长度为%d,具体路径为",i,j,shortPath->pathLen[i][j]);
               printf("%d",i);//输出起点
               k=i;//从起点出发，寻找完整路径
               while(k!=j)
               {
                   k=shortPath->nextVex[k][j];
                   printf("->%d",k);//将途径点输出
               }
               printf("\n");
               /*if(min<shortPath->pathLen[i][j])
               {
                   min=shortPath->pathLen[i][j];
                   maxdistan[i]=min;
               }
               if(i==0)
             {
               printf("%d->%d:%d",i,j,shortPath->pathLen[i][j]);
               printf("\n");
               printf("%d",i);
               k=i;
               while(k!=j)
               {
                   k=shortPath->nextVex[k][j];
                   printf("->%d",k);
               }
               printf("\n");
             }*/
           }
       }
   }
   return 0;
}

算法介绍

Floyd算法用来解决多源最短路径，即可得到图中任意两个结点之间的最短路径。

该算法基于动态规划的思想。假设有n个节点，目标是求节点i到达节点j的最短路径。

每次求的时候，都将节点i到节点j经过k个节点到达最短路径状态记录下来，即d[k][i][j]，意为在状态k下，从节点i经过编号为1、2…k到节点j时路径最短。

当要找下一个节点的最短路径时，使用之前已经记录的状态进行对比，可得到新的状态转移方程

便可以此状态转移方式，遍历所有点之间的情况构造最短路径算法。

题目描述

给定一个 n 个点 m条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定 k个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y的最短距离，如果路径不存在，则输出 impossible。

数据保证图中不存在负权回路。

输入格式

一行包含三个整数 n,m,k。
接下来 m行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
接下来 k行，每行包含两个整数 x,y，表示询问点 x 到点 y的最短距离。

输出格式

共 k行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。

数据范围

1≤n≤200,
1≤k≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。

输入样例：

3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3

输出样例：

impossible
1

题目分析

算法的核心是对所有点的遍历部分，使用三层for循环进行实现。

for(k)			// k为中转点，起始点为1
	for(i)		// i为起始点，起始点为1
		for(j)	// j为目标点，起始点为1
			d[i][j] = min(d[i][j], d[i][k] + d[k][j])

在这里有一个重要的地方，三层for循环的结构虽然简单，但每层for循环的含义必须要按顺序设计，否则将会得到错误的答案。Floyd算法在代码实现上虽然简单但并不是很多人都真正的懂这个算法，原因就在于对于for循环的理解。

这里有两个很赞的答案：

（1）从数学角度

（2）从程序设计角度

参考资料：
Floyd算法为什么把k放在最外层

为什么Floyd算法中k必须放在最外层

算法实现

#include <stdio.h>

const int N = 210, INF = 1e9;       //由于题中权重不超过1e4，因此取INF为1e9（2倍的指数再多一位）
int d[N][N];    // 邻接矩阵

int min(int a, int b)   {   return a < b ? a : b;   }

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

int main(){
    int n, m, q;        scanf("%d%d%d", &n, &m, &q);
    int x, y, z;        // 一对点和权重
    // 初始化邻接矩阵为无穷大
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
           if(i != j)   d[i][j] = INF;
    
    // 获取权重最小的那条边
    while(m--){
        scanf("%d%d%d", &x, &y, &z);
        d[x][y] = min(d[x][y], z);
    }
    floyd(n);
    
    // 查询q对最短路径
    while(q--){
        scanf("%d%d", &x, &y);
        if(d[x][y] > INF / 2)       // 若不存在路径则输出impossible
            puts("impossible");
        else
            printf("%d\n", d[x][y]);
    }
    
    return 0;
}

无注释代码

#include <stdio.h>

const int N = 210, INF = 1e9;

int min(int a, int b)   {   return a < b ? a : b;    }

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

int main(){
    int n, m, q;        
    int x, y, z;
    int d[N][N];
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i != j)  d[i][j] = INF;
            
    while(m--){
        scanf("%d%d%d", &x, &y, &z);
        if(d[x][y] > z)     d[x][y] = z;
    }
    floyd(n, d);
    
    while(q--){
        scanf("%d%d", &x, &y);
        if(d[x][y] > INF / 2)       puts("impossible");
        else    printf("%d\n", d[x][y]);
    }
    
    return 0;
}

时间复杂度为O(n³)

Floyd算法

图:

运算结果 :

代码 :

#include<iostream>
#include<vector>
using namespace std;
const int INF=99999;
class Graph {
	public:
		int N,E;
		int type;
		vector<vector<int> > g;
		Graph(int n=0,int e=0,int type=0) {
			N=n;
			E=e;
			type=type;
			g=vector<vector<int> >(N+1,vector<int>(N+1,INF));
		}
		add(int v,int d,int w=1) {
			g[v][d]=w;
			if(type==1) {
				g[d][v]=w;
			}
		}
		print() {
			for(int i=1; i<=N; i++) {
				for(int j=1; j<=N; j++) {
					cout<<g[i][j]<<" ";
				}
				cout<<endl;
			}
		}

};

void floyd(Graph g) {
	for(int k=1; k<=g.N; k++) {//中介点
		for(int i=1; i<=g.N; i++) {//起点
			for(int j=1; j<=g.N; j++) {//终点
				if(g.g[i][k]+g.g[k][j]<g.g[i][j])
					g.g[i][j]=g.g[i][k]+g.g[k][j];
			}
		}
	}
	for(int i=1; i<=g.N; i++) {
		g.g[i][i]=0;
	}
	g.print();
}
int main(void) {
	Graph g(4,8,0);
	g.add(1,2,2);
	g.add(1,3,6);
	g.add(1,4,4);
	g.add(2,3,3);
	g.add(3,1,7);
	g.add(3,4,1);
	g.add(4,1,5);
	g.add(4,3,12);
	floyd(g);
	return 0;
}