问题描述
若用有向网表示某地区的公路交通网，其中顶点表示该地区的一些主要场所，弧表示已有的公交线路，弧上的权表示票价。试设计一个交通咨询系统，指导乘客以最少花费从该地区中的某一场所到达另一场所。 一、 需求分析
1.本程序要求从文件中读入有向网中顶点的数量和顶点间的票价的矩阵；
2.以用户指定的起点和终点，输出从起点到终点的花费；
3.用Dijkstra算法计算点对点的最短路径；
4.在Dos界面输出起点到终点的花费。
5.测试数据
导线测量法
（文件）
5
－1 10 3 20 －1
－1 －1 －1 5 －1
高压电源设计
－1 2 －1 －1 15
－1 －1 －1 －1 11
－1 －1 －1 －1 －十八大的意义1
（用户）
起点 0
终点 4
输出
18
二、 概要设计
抽象数据类型
typedef struct GraphNode //图的结点
{
int n;
Mark m; //节点的状态 访问 还是未被访问
} GraphNode;
typedef struct Graph //图
{
int n;
GraphNode * Node;
int** edge; //边权信息
} Graph;
算法思想
1、 用图结构来存储公交网络信息。
2、 用户输入顶点数和边权值，使用邻接矩阵存储边权值。
4、 使用Dijkstra算法来计算最短路径长度
5、 输出最短路径
程序的流程
输入模块：输入顶点数和边权值，起点和终点。
输出模块：输出最短路径长度。
三、 详细设计
物理数据类型
typedef struct GraphNode //图的节点
{
int n;
Mark m; //是否被访问
} GraphNode;
typedef struct Graph //图
{
int n;
GraphNode * Node;
int** edge; //边权值
} Graph;
Mark getMark(Graph*G , int i) //返回是否被访问
{
return G->Node[i].m;
}
void setMark(Graph*G,int v,Mark m) //标记为已访问
{
G->Node[v].m=m;
}
int first(Graph*G , int v) //第一个邻结点
{
int i;
for(i=0 ; i<G->n ; i++)
if((G->edge[v][i])!=-1)
return i;
return i;
}
int next(Graph*G , int v , int w) //下一个邻结点
{
int i;
for(i=w+1 ; i<G->n ; i++)
if((G->edge[v][i])!=-1)
return i;
return i;
}
int weight(Graph*G,int v,int w) //返回边权值
{
return G->edge[v][w];
}
int minVertex(Graph*G , int *D) ///寻路径长度最短的那个顶点
{
int i , v;
for(i=0; i<G->n; i++)
if(getMark(G,i)==UNVISITED)
{
v=i;
break;
}
for(i++; i<G->n; i++)
if(getMark(G,i)==UNVISITED&&((((D[i]<D[v])&&D[i]!=-1)||(D[v]==-1))))
v=i;
return v;
}
void Dijkstra(Graph*G , int *D , int s) //Dijkstra算法
{
int i,v,w;
for(i=0; i<G->n; i++)
{
v=minVertex(G,D);
if(D[v]==-1) return; //顶点v的路径长度小于0，即还处于初始状态，还未处理任何顶点，返回
setMark(G,v,VISITED);清分机
for(w=first(G,v); w<G->n; w=next(G,v,w))
if((D[w]>(D[v]+weight(G,v,w)))||(D[w]==-1))
D[w]=D[v]+weight(G,v,w);
}
}
算法流程
输入模块：
输入顶点的数量，再输入各条弧（无边相连的权值都置为-1）。
输出模块：
输出最短路径长度。
反兴奋剂条例
输入输出格式
输入：
（等待用户输入顶点数和边权值）
起点：
终点：
输出：
最短路径：
四、 测试结果
党员二楞妈五、源程序
#include<iostream>
#include<cstdlib>
using namespace std;
enum Mark {UNVISITED,VISITED};
typedef struct GraphNode //图的节点
{
int n;
Mark m; //是否被访问
} GraphNode;
typedef struct Graph //图
{
int n;
GraphNode * Node;
int** edge; //边权值
} Graph;
Mark getMark(Graph*G , int i) //返回是否被访问
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议