交通咨询系统中的最短路径 建立交通图的存储结构、解决单源最短路径问题、再实现两个地点最短路径问题

发布网友 发布时间：2022-05-15 18:48

我来回答

共1个回答

热心网友 时间：2024-02-26 23:12

交通图应该是带权值的有向图问题。
#include <iostream.h>
#include <iomanip.h>
#include <stdio.h>

#define Maxint 9999
#define Maxn 30 //最大顶点数目

int CostMatrixArr[Maxn][Maxn]; //邻接表
int dist[Maxn]; //最短路径长度
int pre[Maxn]; //最短路径顶点

//Dijkstra方法求最短路径
// n--顶点总数
// k--起始顶点
void Dijkstra(int CostMatrix[][Maxn],int n,int k,int dist[],int pre[])
{
bool s[Maxn];
int i,j,p,min;

for(i=0;i<n;i++)
{ s[i]=false;
pre[i]=k-1;
dist[i]=CostMatrix[k-1][i];
}
s[k-1]=true;pre[k-1]=0;dist[k-1]=0;
for(j=0;j<n-1;j++)
{
min=Maxint;
p=-1;
for(i=0;i<n;i++)
if(!s[i] && dist[i]<min)
{ p=i;min=dist[i];
}
if(p==-1)break;
s[p]=true;
for(i=0;i<n;i++)
if(!s[i] && min+CostMatrix[p][i]<dist[i])
{ dist[i]=min+CostMatrix[p][i];
pre[i]=p;
}
}
}

//显示最短路径：从BeginVertext到EndVertex的顶点列表
void DispPath(int pre[],int BeginVertext,int EndVertex)
{
if(EndVertex!=BeginVertext)
DispPath(pre,BeginVertext,pre[EndVertex-1]+1);
cout<<EndVertex<<' ';
}

//显示创建的邻接表
void DispAdjlink(int CostMatrix[][Maxn],int n)
{
int i,j;
char s[10];
//表头
cout<<"顶点";
for(i=0;i<n;i++)cout<<setw(3)<<i+1;
cout<<endl;

//邻接表
for(i=0;i<n;i++)
{ sprintf(s," V%-2d",i+1);
cout<<s;
for(j=0;j<n;j++)
if(CostMatrixArr[i][j]==Maxint)
cout<<" ∞";
else
cout<<setw(3)<<CostMatrixArr[i][j];
cout<<endl;
}
}

void main()
{
int n=0,V,U,W,x;
for(int i=0;i<Maxn;i++) //初始化邻接表
for(int j=0;j<Maxn;j++)
CostMatrixArr[i][j]=Maxint;
cout<<"顶点编号从1开始。\n================\n";
cout<<"顶点、终点、权值：\n";
do
{
cin>>V>>U>>W;
if(!(V && U && W))break; //若输入的顶点号或权值为0，结束
CostMatrixArr[V-1][U-1]=W; //存入邻接表
n=n>=(V>U?V:U)?n:(V>U?V:U); //n为输入的最大顶点号,即顶点个数
}while(1);
cout<<"顶点数为："<<n<<endl;

DispAdjlink(CostMatrixArr,n); //显示邻接表

Dijkstra(CostMatrixArr,n,1,dist,pre); //用Dijkstra求最短路径

//从顶点1到最后一个顶点的最短径
cout<<"最短路径:";
DispPath(pre,1,n);
cout<<"\n";

//从顶点1到最后一个顶点的权值
cout<<"权值:"<<dist[n-1]<<endl;
}