【算法】图的应用之求两个城市间的最短路径--FloydWarshall算法

约定不等于承诺〃 2022-06-13 07:36 224阅读 0赞

题目是这样的，如下图所示，一共有4个城市，8条公路。

有的城市建有直接的公路，而有的城市则没有，公路之间的数字显示的是长度。

由此，可以算出一个城市到另外一个城市的最短路径。

![Center][]

代码的实现：

#define _CRT_SECURE_NO_DEPRECATE
    #include<stdio.h>
    #include<stdlib.h>
    int main()
    {
    	int e[10][10], k, i, j, n, m, t1, t2, t3;
    	int inf = 99999999;
    	printf("请输入顶点数n和边数m->\n");
    	scanf("%d %d", &n, &m);
    
    	//初始化
    	for (i = 1; i <= n; i++)
    	{
    		for (j = 1; j<= n; j++)
    		{
    			if (i == j)
    			{
    				e[i][j] = 0;
    			}
    			else
    			{
    				e[i][j] = inf;
    			}
    		}
    	}
    
    	printf("请输入顶点t1，顶点t2，以及t1和t2之间的距离->\n");
    	for (i = 1; i <= m; i++)
    	{
    		scanf("%d %d %d", &t1, &t2, &t3);
    		e[t1][t2] = t3;;
    	}
    
    	for (k = 1; k <= n; k++)
    	{
    		for (i = 1; i <= n; i++)
    		{
    			for (j = 1; j <= n; j++)
    			{
    				if (e[i][j] > e[i][k])
    				{
    					e[i][j] = e[i][k] + e[k][j];
    				}
    			}
    		}
    	}
    	printf("     ");
    	for (i = 1; i <= n; i++)
    	{
    		printf("%5d", i);
    	}
    	printf("\n");
    	for (i = 1; i <= n; i++)
    	{
    		printf("%5d", i);
    		for (j = 1; j <= n; j++)
    		{
    			printf("%5d", e[i][j]);
    		}
    		printf("\n");
    	}
    	system("pause");
    	return 0;
    }

运行的结果如下：

![Center 1][]

[Center]: /images/20220613/c163c49efe8e49f498c8d8fe24d43895.png
[Center 1]: /images/20220613/1808b8b37fe043fb81eead7645700f8e.png