有關數據結構的C++程序-城市交通最短路徑問題

ID:544053 · 發表于 2019-5-21 18:31

設計一個交通查詢系統，能讓游客查詢從任一城市頂點到另一城市頂點之間的最短路徑或最低花費或最少時間等問題。對于不同查詢要求，可輸入城市間的路程或所需時間或所需費用。
本程序共分三個部分：
（1）建立交通網絡圖的存儲結構；
（2）單源最短路徑；
（3）實現兩個城市頂點之間的最短路徑。

單片機源程序如下:

#include <stdio.h>
#include <stdlib.h>
#define MVNum 100
#define Maxint 32767
enum boolean{FALSE,TRUE};
typedef char VertexType;
typedef int Adjmatrix;
typedef struct {
VertexType vexs[MVNum];
Adjmatrix arcs[MVNum][MVNum];
}MGraph;
int D1[MVNum],P1[MVNum];
int D[MVNum][MVNum],P[MVNum][MVNum];
//文件名CreateMGraph.c
void CreateMGraph(MGraph *G,int n,int e)
{//采用鄰接矩陣表示法構造有向圖G，n，e表示圖的當前頂點數和邊數
int i,j,k,w;
for(i=1;i<=n;i++)
G->vexs[i]=(char)i;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
G->arcs[i][j]=Maxint;//初始化鄰接矩陣
printf("輸入%d條邊的i、j及w:\n",e);
for(k=1;k<=e;k++)
{
scanf("%d,%d,%d,",&i,&j,&w);
G->arcs[i][j]=w;
}
printf("有向圖的存儲結構建立完畢\n");
}
//文件dijkstra.c
void Dijkstra(MGraph *G ,int v1,int n)
{
int D2[MVNum],P2[MVNum];
int v,i,w,min;
enum boolean S[MVNum];
for(v=1;v<=n;v++)
{
S[v]=FALSE;
D2[v]=G->arcs[v1][v];
if(D2[v]<Maxint)
P2[v]=v1;
else
P2[v]=0;
}
D2[v1]=0;
S[v1]=TRUE;
for(i=2;i<n;i++)
{
min=Maxint;
for(w=1;w<=n;w++)
if(!S[w]&& D2[w]<min)
{
v=w;
min=D2[w];
}
S[v]=TRUE;
for(w=1;w<=n;w++)
if(!S[w] && (D2[v]+G->arcs[v][w]<D2[w]))
{
D2[w]=D2[v]+G->arcs[v][w];
P2[w]=v;
}
}
printf("路徑長度路徑\n");
for(i=1;i<=n;i++)
{
printf("%5d",D2[i]);
printf("%5d",i);
v=P2[i];
while(v!=0)
{
printf("<-%d",v);
v=P2[v];
}
printf("\n");
}
}
//文件floyd.c
void Floyd(MGraph *G,int n)
{
int i,j,k,w;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(G->arcs[i][j]!=Maxint)
P[i][j]=j;
else
P[i][j]=0;
D[i][j]=G->arcs[i][j];
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(D[i][k]+D[k][j]<D[i][j])
{
D[i][j]=D[i][k]+D[k][j];
P[i][j]=P[i][k];
}
}
}
}
void main()
{
MGraph *G;
int m,n,e,v,w,k;
int xz=1;
G=(MGraph *)malloc(sizeof(MGraph));
printf("輸入圖中頂點個數和邊數n,e:");
scanf("%d,%d",&n,&e);
CreateMGraph(G,n,e);
while(xz!=0)
{
printf("********求城市之間的最短路徑********\n");
printf("====================================\n");
printf("1.求一個城市到所有城市的最短路徑\n");
printf("2.求任意的兩個城市之間的最短路徑\n");
printf("====================================\n");
printf("請選擇： 1、或 2、選擇 0、退出：");
scanf("%d",&xz);
if(xz==2)
{
Floyd(G,n);
printf("輸入源點(或稱起點)和終點:v,w:");
scanf("%d,%d",&v,&w);
k=P[v][w];
if(k==0)
printf("頂點%d到%d無路徑!\n",v,w);
else
{
printf("從頂點%d到%d的最短路徑是：%d!\n",v,w,v);
while(k!=w)
{
printf("->%d",k);
k=P[k][w];
}
printf("->%d",w);
printf("路徑長度:%d\n",D[v][w]);
}
}
else
if(xz==1)
{
printf("求單源路徑，輸入源點v:");
^^^^^限于篇幅余下內容下載附件^^^^^^

復制代碼

全部資料51hei下載地址：

程序.rar (1.29 KB, 下載次數: 11)

帳號		自動登錄	找回密碼
密碼			立即注冊

久久久久久久999_99精品久久精品一区二区爱城_成人欧美一区二区三区在线播放_国产精品日本一区二区不卡视频_国产午夜视频_欧美精品在线观看免费

有關數據結構的C++程序-城市交通最短路徑問題

評分