公园景点导游问题Dijkstra求最短路径Word版

1、传播优秀word版文档 ，希望对您有帮助，可双击去除！公园主要游览景点导游问题。问题描述：对某公园主要游览景点导游。功能需求：要求完成以下功能：1.将公园内各景点输出。2.将公园内每两个位置（若两个位置之间有直接路径）的距离输出。3.修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输出每两个位置（若两个位置之间有直接路径）的距离；4.求最短路径：输出给定两点之间的最短路径的长度及途经的地点，输出任意一点与其他各点的最短路径；5.删除：删除任意一条边。6.插入：插入任意一条边。代码#include <stdio.h> #include <iostream.h>

2、#include<stdlib.h> #include<conio.h> #include <malloc.h> #include<string.h> #define max 1000#define length 6#define value int typedef struct char name30; int num; vextype; typedef struct vextype vexslength; value arcslengthlength; int vexnum,arcnum ; mgraph;mgraph b; mgraph i

3、nitgraph() int i, j; mgraph g;g.vexnum =6; /初始景点数为6，即图的顶点数g.arcnum =15; /初始景点最大路径数为15 ，即图的最大边数for(i=0;i<g.vexnum;i+) g.vexsi.num=i; strcpy(g.,"景点a"); /景点astrcpy(g.,"景点b"); /景点bstrcpy(g.,"景点c"); /景点cstrcpy(g.,"景点d"); /

4、景点dstrcpy(g.,"景点e"); /景点estrcpy(g.,"景点f"); /景点ffor(i=0;i<g.vexnum;i+) for(j=0;j<g.vexnum;j+) g.arcsij=max;g.arcs01=50; /景点a与景点b的距离为 50g.arcs02=20; /景点a与景点c的距离为 20g.arcs03=30; /景点a与景点d的距离为 30g.arcs12=10; /景点b与景点c的距离为 10g.arcs14=70; /景点b与景点e的距离为 70g.arcs25

5、=90; /景点c与景点f的距离为 90g.arcs35=40; /景点d与景点f的距离为 40g.arcs45=50; /景点e与景点f的距离为 50for(i=0;i<g.vexnum;i+) for(j=0;j<g.vexnum;j+) g.arcsji=g.arcsij;return g;void menu() /功能需求选项菜单 cout<<"*功能需求选项菜单*n" cout<<" 1-输出公园内景点n" cout<<" 2-输出每两个直接相连景点的距离n" cout<

6、<" 3-修改两个景点距离n" cout<<" 4-两景点之间最短路径n" cout<<" 5-删除某条边（两个直接相连景点的连线）n" cout<<" 6-插入某条边n" cout<<" 0-退出n" cout<<"*某公园主要游览景点导游*n" void putoutvex(mgraph *g) /功能 1 输出公园内景点cout<<"公园内各景点"<<endl;

7、for(int i=0;i<g->vexnum;i+)cout<<g-><<" " <<endl; void putoutarc(mgraph *g) /功能 2 输出公园内每两个直接相连景点的距离for(int i=0;i<g->vexnum;i+) for(int j=0;j<g->vexnum;j+) if(g->arcsij<max) cout <<g-><<"->"<<

8、g-><<"的距离为 " <<g->arcsij<<endl; void change(mgraph *g) /功能 3 修改：修改两个景点距离（权值） int v0,v1,length; cout<<"修改：输入两顶点n" cin>>v0; cin>>v1; cout<<"输入距离:" cin>>length; g->arcsv0v1=g->arcsv1v0=length;void dijkst

9、ra(mgraph * g) /功能 4.求最短路径 输出给定两景点之间的最短路径的长度及途经的各景点 /使用dijkstra算法求解最短路径 int v,w,i,min,t=0,x,v0,v1; int final20, d20, p2020; cout<<"请输入起始顶点:n" cin>>v0; if(v0<0|v0>g->vexnum) cout<<"此点不存在!请重新输入顶点:" cin>>v0; cout<<"请输入结束顶点:n" cin>&

10、gt;v1; if(v1<0|v1>g->vexnum) cout<<"此点不存在!请重新输入顶点:" cin>>v1; for(v=0;v<g->vexnum;v+) finalv=0; dv=g->arcsv0v; for(w=0;w<g->vexnum;w+) pvw=0; if(dv<max) pvv0=1;pvv=1; dv0=0;finalv0=1; for(i=1;i<g->vexnum;i+) min=max; for(w=0;w<g->vexnum;w+)

11、 if(!finalw) if(dw<min)v=w;min=dw; finalv=1; for(w=0;w<g->vexnum;w+) if(!finalw&&(min+g->arcsvw<dw) dw=min+g->arcsvw; for(x=0;x<g->vexnum;x+) pwx=pvx; pww=1; cout<<"从"<<g-><<"到"<<g-><<"

12、的最短路径长度为："<<dv1<<endl; cout<<"途经的景点："<<endl; for(int j=0;j<g->vexnum;j+) if(pv1j=1) cout<<g-><<endl; void deletearc(mgraph *g) /功能 5 删除：删除任意一条边。 int v0,v1; cout<<"请输入两顶点:n" cin>>v0>>v1; g->arcsv0v1=m

13、ax; g->arcsv1v0=max;void insertarc(mgraph *g) /功能 6 插入：插入任意一条边。 int v0,v1,l=0; cout<<"请输入两顶点:n" cin>>v0>>v1; cout<<"请输入路径长度:n" cin>>l; g->arcsv0v1=l; g->arcsv1v0=l;void main() int a; b=initgraph(); menu(); cin>>a; while(a!=0) switch(a) case 1:putoutvex(&b);menu();break; case 2:putoutarc(&b);menu();break; case 3:change(&b);menu();break; case 4:dijkstra(&b);menu();break; case 5:deletearc(&b);menu();break; case 6:insertarc(&b);menu();break; case 0: