关于离散数学中的Floyd-Warshall算法求两个节点间的最短路径问题

Question

不太清楚应该做这样的题目的，只知道应该根据所给出的图写出接邻矩阵，然后应该怎样做？图是有向图，每条边都有权值的。求高手给个解题步骤。

Answer 1

在离散数学中用的warshall算法，应该是用来求传递闭包的吧。
你如果想解决最短路径问题，可以参考专门讲算法的书（如：《算法概论》），可以用Warshall算法，动态规划，分支定界等等很多算法解决这个问题。

Answer 2

#include<stdio.h>
#include<string.h>
const int MAX=100;
int g[MAX][MAX];
void floyd(int n)///弗洛易德算法
{
int i,j,k;
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
{
if(i==k)continue;
for(j=0;j<n;j++)
{
if(i==j||j==k)continue;
if(g[i][k]+g[k][j]<g[i][j])
g[i][j]=g[i][k]+g[k][j];
}
}
}
}
int main()
{
int i,j,n;
scanf("%d",&n);///输入顶点数
for(i=0;i<n;i++)///输入邻接矩阵
{
for(j=0;j<n;j++)
{
scanf("%d",&g[i][j]);
}
}
floyd(n);
return 0;
}本回答被网友采纳

Answer 3

你试着去用图灵机设想出来的模型解决吧，听说该模型什么数学问题都有可以解决的。