中文XML论坛--[求助]迪杰斯特拉算法和佛洛伊德算法

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

我要设计一个交通咨询系统设计（最短路径问题）

用人们熟悉的交通咨询系统实例来验证迪杰斯特拉算法和佛洛伊德算法。
设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径或最低费用或最少时间等问题。对于不同咨询要求，可以输入城市间的路程或所需要时间或所需费用。设计分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。

各位高手有这两个算法的相关例子代码发上来,急用,谢谢!~~

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

没人顶,自己顶上

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

#include<iostream>
using namespace std;

const int len = 8;
const double infinite = 3.14E38;//用一个比较大的浮点数表示无穷大
void shortest_route(double *Graph[],int n,int u,double *d,int *p);//n为顶点的个数,u为原点

int main(void)
{
double *Graph[len];
int i,j;

for(i = 0; i < len; i ++)
Graph[i] = new double[len];

for(i = 0; i < len; i ++)
for(j = 0; j < len; j ++)
Graph[i][j] = infinite;//初始化

double ev;
cin>>i>>j>>ev;
while(i>=0 && j>=0 && i<len && j<len)
{
Graph[i][j] = ev;
cin>>i>>j>>ev;
}

int u;
cin>>u;
double *d = new double[len];
int *p = new int[len];
shortest_route(Graph,len,u,d,p);

for(i = 0; i < len; i ++)
{
  if(p[i] != -1)
  {
   cout<<"the node of place "<<i<<" is: "<<p[i]<<endl;
   cout<<"the shortest distance from "<<u<<" to "<<i<<" is: "<<d[i]<<"\n"<<endl;
  }
}

for(i = 0; i < len; i ++)
delete []Graph[i];

delete []p;
delete []d;

// main();

return 0;
}

void shortest_route(double *Graph[],int n,int u,double *d,int *p)
{
int i, x;
int j;
bool *s = new bool[n];
double minev;

for(i = 0; i < n; i ++)
{
d[i] = Graph[u][i];
s[i] = false;

  if((d[i] < infinite) && (i != u))
   p[i] = u;
  else
   p[i] = -1;
}
s[u] = true;

for(i = 1; i < n; i ++)
{
  minev = infinite;
  for(j = 0; j < n; j ++)
   if((!s[j]) && (minev > d[j]))
   {
    minev = d[j];
    x = j;
   }

if(minev == infinite)
return;

s[x] = true;

  for(j = 0; j < n; j ++)
   if((!s[j]) && (Graph[x][j] < infinite) && (d[x] + Graph[x][j] < d[j]))
   {
    d[j] = d[x] + Graph[x][j];
    p[j] = x;
   }
}

delete []s;
}

//数据结构教材上的只有一个迪杰斯特拉算法的

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

谢谢你~~！！！

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

不客气，很喜欢和大家一起交流相互学习

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

floyed:

for(int k=1;k<=m;k++)
for (int i=1;i<=m;i++)
  if (i<>k)
   for (int j=1;j<=m;j++)
     if (i<>j)&&(j<>k) dist[i][j]=min(dist[i][j],dist[i][k]+dist[j][k]);

类似无向图传递闭包的算法。

其实中学竞赛的书里面有江这个的，但是没有证明。

p.s.
我c++不是很好,可能有错,请见谅……

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	93.750ms