#include<stdio.h>
#define MAXVEX 100
typedef char VexType
typedef float AdjType
typedef struct
{ VexType vexs[MAXVEX]/* 顶点信息 */
AdjType arcs[MAXVEX][MAXVEX]/* 边信息 */
int n/* 图的顶点个数 */
}GraphMatrix
GraphMatrix graph
typedef struct {
VexType vertex/* 顶点信息 */
AdjType length/* 最短路径长度 */
int prevex/* 从v0到达vi(i=1,2,…n-1)的最短路径上vi的前趋顶点 */
}Path
Path dist[6]/* n为图中顶点个数*/
#define MAX 1e+8
void init(GraphMatrix* pgraph, Path dist[])
{
int idist[0].length=0dist[0].prevex=0
dist[0].vertex=pgraph->vexs[0]
pgraph->arcs[0][0]=1/* 表示顶点v0在集合U中 */
for(i=1i<pgraph->ni++) /* 初始化集合V-U中顶点的距离值 */
{ dist[i].length=pgraph->arcs[0][i]
dist[i].vertex=pgraph->vexs[i]
if(dist[i].length!=MAX)
dist[i].prevex=0
else dist[i].prevex= -1
}
}
void dijkstra(GraphMatrix graph, Path dist[])
{ int i,j,minvexAdjType min
init(&graph,dist)/* 初始化，此时集合U中只有顶点v0*/
for(i=1i<graph.ni++)
{ min=MAXminvex=0
for(j=1j<graph.nj++)
if( (graph.arcs[j][j]==0) &&(dist[j].length<min) ) /*在V-U中选出距离值最小顶点*/
if(minvex==0) break/* 从v0没有路径可以通往集合V-U中的顶点 */
graph.arcs[minvex][minvex]=1/* 集合V-U中路径最小的顶点为minvex */
for(j=1j<graph.nj++) /* 调整集合V-U中的顶点的最短路径 */
{ if(graph.arcs[j][j]==1) continue
if(dist[j].length>dist[minvex].length+graph.arcs[minvex][j])
{ dist[j].length=dist[minvex].length+graph.arcs[minvex][j]
dist[j].prevex=minvex
}
}
}
}
void initgraph()
{
int i,j
graph.n=6
for(i=0i<graph.ni++)
for(j=0j<graph.nj++)
graph.arcs[i][j]=(i==j?0:MAX)
graph.arcs[0][1]=50
graph.arcs[0][2]=10
graph.arcs[1][2]=15
graph.arcs[1][4]=5
graph.arcs[2][0]=20
graph.arcs[2][3]=15
graph.arcs[3][1]=20
graph.arcs[3][4]=35
graph.arcs[4][3]=30
graph.arcs[5][3]=3
graph.arcs[0][4]=45
}
int main()
{
int i
initgraph()
dijkstra(graph,dist)
for(i=0i<graph.ni++)
printf("(%.0f %d)",dist[i].length,dist[i].prevex)
return 0
}
}
}
}
void initgraph()
{
int i,j
graph.n=6
for(i=0i<graph.ni++)
for(j=0j<graph.nj++)
graph.arcs[i][j]=(i==j?0:MAX)
graph.arcs[0][1]=50
graph.arcs[0][2]=10
graph.arcs[1][2]=15
graph.arcs[1][4]=5
graph.arcs[2][0]=20
graph.arcs[2][3]=15
graph.arcs[3][1]=20
graph.arcs[3][4]=35
graph.arcs[4][3]=30
graph.arcs[5][3]=3
graph.arcs[0][4]=45
}
int main()
{
int i
initgraph()
dijkstra(graph,dist)
for(i=0i<graph.ni++)
printf("(%.0f %d)",dist[i].length,dist[i].prevex)
return 0
}
这个稍作改动就可以了。
这是我们的一个实验，你可以参考一下一、 需求分析
【问题描述】
设计一个校园导游程序，为来访的客人提供各种信息查询服务。
【基本要求】
（1） 设计你所有学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。
（2） 为来访客人提供图中任意景点相关信息的查询。
（3） 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
【测试数据】
由读者根据实际情况指定。
二、概要设计
本次实验中运用到的数据类型有：图，顶点，边结点
typedef struct edgenode
{
int adjvex //临接点序号
int length //道路长度
char name[20] //景点名称
char info[100]//景点详细信息
struct edgenode *next
}edgenode, *Node
typedef struct
{
char data[20] //存储景点的名称.
char str[100] //具体的介绍此景点
struct edgenode *link//指向下一个景点
}vexnode //景点及其信息.
typedef struct Edge
{
int lengh //边的权值，表示路径长度.
int ivex, jvex //边的两端顶点号
struct Edge *next //指向下一条边
} EdgeType //边及其信息.
typedef struct
{
int num //顶点编号
char data[20] //顶点名称
} vertex
typedef struct{
vertex vexs[MAX] //顶点集合
int edges[MAX][MAX] //邻接矩阵
}adjmax
基本 *** 作：
void fun()
// *** 作结果：功能说明并显示所有景点
void creatgraph(vexnode g[],int &n, EdgeType e[],adjmax &adj)
// *** 作结果：创建校园图
void travgraph(vexnode g[],int n,adjmax adj)
//初始条件：已知邻接表adj和顶点g及其数目n
// *** 作结果：查找指定景点信息
void Ppath(int path[][MAX],int i,int j,vexnode g[])
// *** 作结果：寻找最短路径
void Dispath(int A[][MAX],int path[][MAX],int n,vexnode g[])
//初始条件：已知顶点g和数目n及其权值
// *** 作结果：显示最短路径
void Floyd(adjmax adj,int n,vexnode g[])
//初始条件：已知邻接表adj和顶点g
// *** 作结果：Floyd算法计算所有两个景点间最短路径
三、详细设计
1、---------main()---------
char choice
int n = 0 / /景点数目
vexnode g[MAX] //保存顶点及其信息
EdgeType e[MAXedg] //保存边及其信息
adjmax adj//保存边和定点
creatgraph(g,n,e,adj) //建立校园导游图
while(1)
{
do{
system("cls")
fun() //功能说明
printf("请输入所要进行的 *** 作：")
choice=getch()
printf("\n") }while(choice!='s'&&choice!='S'&&choice!='v'&&choice!='V'&&choice!='Q'&&choice!='q')
switch(choice)
{
case('s'):
case('S'): Floyd(adj,n,g) //查找最短路径
break
case('v'):
case('V'):travgraph(g,n,adj)//景点查询
break
case('q'):
case('Q'):return //结束程序
}
}
2、------- travgraph()---------
void travgraph(vexnode g[],int n,adjmax adj)
{
int i = 1,flag = 1,num //num存储要查询的景点的序号
char ch
edgenode *p
printf("请输入您要查询的景点序号:\n")
scanf("%d",&num)
while(i <= n) //遍历邻接表
{
p = g[i].link
if(i == num &&flag == 1)
{
printf("此景点的名称是: %s\n",g[i].data)
printf("此景点的介绍是: %s\n",g[i].str)
printf("是否继续? Y/N")
ch=getch()
printf("\n")
if(ch == 'Y' || ch == 'y') //继续
{
flag = 1
i = 1
printf("请输入您要查询的景点序号:\n")
scanf("%d",&num)
getchar()
}
else
flag = 0 //不继续
}
else
i++
}
}3、------- Floyd()---------
//Floyd算法计算所有两个景点间最短路径
void Floyd(adjmax adj,int n,vexnode g[])
{
int A[MAX][MAX],path[MAX][MAX] //A是路径长度，path是路径。
int i,j,k
for(i = 1i <= ni++) //初始化
for(j = 1j <= nj++)
{
A[i][j] = adj.edges[i][j] //i j之间长度
if(i == j)
{
A[i][j] = 0
}
path[i][j] = -1 //初始化
}
for(k = 1k <= nk++)
for(i = 1i <= ni++)
for(j = 1j <= nj++)
{
if(A[i][j] >(A[i][k] + A[k][j]))
{
A[i][j] = A[i][k]+A[k][j] //修改最短路径长度值
path[i][j] = k//将最短路径的节点号保存
}
}
Dispath(A,path,n,g) //用户输入，查找任意两个景点间的最短路径。
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）