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

交通图应该是带权值的有向图问题。#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;}