Question

还记得基于Dijkstra算法的最短路径问题求解这道题吗

我这题是把第二步换成采用Floyd算法求每一对顶点的最短路径 其他都是一样的 我在做课程设计 这个算法根本就是书上没有的 老师偏让我做 看到你曾经帮过别人 能帮帮我吗
进行类的设计与实现，解决最短路径问题。具体要求如下：
（1）采用图的邻接矩阵或邻接表实现最短路径问题中图的存储；
（2）采用Floyd算法求从每一对顶点的最短路径；
（3）将上述功能作为类的成员函数实现，编写主函数测试上述功能。
（4） 用C++编写，需要主函数

Answer 1

Dijkstra 带输出路径，邻接表存图。。。以前写的代码。
int a[1000001],b[1000001],c[1000001];
int first[1000001],next1[1000001];
int g[1001];
int f[1001];
bool bo[1001];

int main()
{
// for (int i=0;i<1000000;i++)
// next1[i]=-1;
for (int i=1;i<=1000;i++)
f[i]=855993460;
int n,m;
cin>>n>>m;
for (int i=1;i<=m;i++)
{
cin>>a[i]>>b[i]>>c[i];
next1[i]=first[a[i]];
first[a[i]]=i;

}
int v=1;
f[v]=0;
for (int i=1;i<=n;i++)
{
for (int j=first[v];j!=0;j=next1[j])
if (f[v]+c[j]<f[b[j]]&&bo[b[j]]==false)
{
g[b[j]]=v;
f[b[j]]=f[v]+c[j];
}
int minnum=855993460,minv;
for (int i=1;i<=n;i++)
if (f[i]<minnum&&bo[i]==false)
minnum=f[i],minv=i;
v=minv;
bo[v]=true;
}
cout<<f[n]<<endl;

int k=n;
stack<int> sta;
while (k!=0)
{
sta.push(k);
k=g[k];
}
cout<<sta.top();
sta.pop();
while (!sta.empty())
{
cout<<"==>"<<sta.top();
sta.pop();
}
// system("PAUSE");
return 0;
}

追问

用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;
}

Answer 2

Floyd算法是是一种用于寻找给定的加权图中顶点间最短路径的算法。具体用法你看看这个就会了，很详细的http://www.cnblogs.com/twjcnblog/archive/2011/09/07/2170306.html