我这题是把第二步换成采用Floyd算法求每一对顶点的最短路径 其他都是一样的 我在做课程设计 这个算法根本就是书上没有的 老师偏让我做 看到你曾经帮过别人 能帮帮我吗
进行类的设计与实现,解决最短路径问题。具体要求如下:
(1)采用图的邻接矩阵或邻接表实现最短路径问题中图的存储;
(2)采用Floyd算法求从每一对顶点的最短路径;
(3)将上述功能作为类的成员函数实现,编写主函数测试上述功能。
(4) 用C++编写,需要主函数
用Floyd算法会吗?老师要求用Floyd 谢谢了
追答..........
floyed不是更简单吗?比dijkstra或SPFA简单,但是是O(n^3)
这是核心代码。
f[i][j]表示i到j的最短路
for (int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (f[i][k]+f[k][j]<f[i][j])
f[i][j]=f[i][k]+f[k][j];
能帮我写一下全部程序吗 我真的一点都不会 谢谢您了
追答这个是网上找的,不过也差不多,看了一下是没有读图的,你自己加上输入吧,下午忙,要我写的话晚上可以给你写一个,其实很简单的。
//每对顶点之间的最短路径 Folyed
#include
#define MAXVEX 6
#define INF 32767
void Floyed(int cost[][MAXVEX],int n)
{
int A[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];
int i,j,k,pre;
for(i = 0;i A[i][k] + A[k][j])
{
A[i][j] = A[i][k] + A[k][j];
path[i][j] = k;
}
}
cout " << j << ":";
if(A[i][j] == INF)
{
if(i != j)
cout << "不存在路径" << endl;
}
else
{
cout << "路径长度为:" << " " << A[i][j];
cout << " 路径为" << i << " ";
pre = path[i][j];
while(pre != -1)
{
cout << pre << " ";
pre = path[pre][j];
}
cout << j << endl;
}
}
}
void main()
{
int cost[6][MAXVEX] = {
{0,50,10,INF,INF,INF},
{INF,0,15,50,10,INF},
{20,INF,0,15,INF,INF},
{INF,20,INF,0,35,INF},
{INF,INF,INF,30,0,INF},
{INF,INF,INF,3,INF,0},
};
Floyed(cost,6);
cout << endl;
}