有尝求Floyd 算法编程，演算我的手写过程！
急 本人不会编程，是在校高中生。
数学论文用的是弗洛伊德矩阵摹乘法算的做的一个选址问题的最优化。
想用Floyd Warshall algorithm去验算一下算出来的结果是否是正确的，哪位可以有尝帮我编一下这方面的程序吗，原始数据如下。
算法开始：
算法结束数据
详情可以微信：zhengzheng0826
经验证，你手算的结果是正确的。
// C Program for Floyd Warshall Algorithm
#include <stdio.h>
// Number of vertices in the graph
#define V 7
/* Define Infinite as a large enough
value. This value will be used
for vertices not connected to each other */
#define INF 99999
// A function to print the solution matrix
void printSolution(int dist[][V]);
// Solves the all-pairs shortest path
// problem using Floyd Warshall algorithm
void floydWarshall(int graph[][V])
{
/* dist[][] will be the output matrix
that will finally have the shortest
distances between every pair of vertices */
int dist[V][V], i, j, k;
/* Initialize the solution matrix
same as input graph matrix. Or
we can say the initial values of
shortest distances are based
on shortest paths considering no
intermediate vertex. */
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
/* Add all vertices one by one to
the set of intermediate vertices.
---> Before start of an iteration, we
have shortest distances between all
pairs of vertices such that the shortest
distances consider only the
vertices in set {0, 1, 2, .. k-1} as
intermediate vertices.
----> After the end of an iteration,
vertex no. k is added to the set of
intermediate vertices and the set
becomes {0, 1, 2, .. k} */
for (k = 0; k < V; k++)
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on the shortest path from
// i to j, then update the value of
// dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
// Print the shortest distance matrix
printSolution(dist);
}
/* A utility function to print solution */
void printSolution(int dist[][V])
{
printf(
"The following matrix shows the shortest distances"
" between every pair of vertices \n");
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf("%7d", dist[i][j]);
}
printf("\n");
}
}
// driver's code
int main()
{
int graph[V][V] = {
{0, INF, INF, INF, 10, INF, 5},
{INF, 0, 6, 7, 9, INF, INF},
{INF, 6, 0, 6, 4, INF, INF},
{INF, 7, 6, 0, INF, 8, 5},
{10, 9, 4, INF, 0, 7, 7},
{INF, INF, INF, 8, 7, 0, INF},
{5, INF, INF, 5, 7, INF, 0}};
// Function call
floydWarshall(graph);
return 0;
}
$ gcc -Wall main.c
$ ./a.out
The following matrix shows the shortest distances between every pair of vertices
0 17 14 10 10 17 5
17 0 6 7 9 15 12
14 6 0 6 4 11 11
10 7 6 0 10 8 5
10 9 4 10 0 7 7
17 15 11 8 7 0 13
5 12 11 5 7 13 0
- 这篇文章讲的很详细，请看：最短路之Floyd算法
如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^
Floyd 求点 S 到 点 T 的最短路，其他问题要的话也可以私信我要哦~
#include <bits/stdc++.h>
using namespace std;
#define N 1001
int maxV=1e9;
int n,m,s,t;
int dist[N][N];
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
dist[i][j]=maxV;
}
dist[i][i]=0;
}
for (int i=1;i<=m;i++)
{
int x,y,d;
cin>>x>>y>>d;
dist[x][y]=d;
dist[y][x]=d;
}
for (int k=1;k<=n;k++)
{
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
cin>>s>>t;
cout<<dist[s][t]<<" ";
return 0;
}