图论最短路

图论最短路 最短路径问题 问题描述: 若用有向网示某地区的公路交通网～其中顶点表示该地区的一些主要场所～弧表示已有的公交线路～弧上的权表示票价。试一个交通咨询系统～指导乘客以最少花费从该地区中的某一场所到达另一场所。 基本要求: ,1, 从文件中读入有向网中顶点的数量和顶点间的票价的矩阵。 ,2, 以用户指定的起点和终点～输出从起点到终点的花费。 需求分析: 1、输入形式: 第一行输入一个整数n～表示n个结点 从第2行到第n+1行每行输入n个数据为图的邻接矩阵 需要注意的是结点从0开始编号 ～分别表示结点s到结点t的编号 接下来是两个整数s和t 2、输出形式: 输出只有一个数据～为从起点s到结点t的最短路径长度 3、功能描述: 就路径相应的权值而言～只要用户输入相应的边的权值～给出 用户的起止点需求～可以给出用户最优的选择～告知其最小的 花费数额有多大。 4、样例输入输出: 输入: 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 5、效率分析:O(n^2)(n为节点数目) 抽象数据结构, ADT,: 采用Dijkstra算法实现最短路的时候常常采用邻接矩阵来存储数据 抽象数据结构类型描述: Struct vertex{ Itn num;//节点数目 Char data;//节点信息 }; Typedef struct graph{ Itn n;//顶点数 Int e;//边数 Struct vertex vexs[MaxSize]; //顶点数组 Itn edg[MaxSize][MaxSize]; //邻接矩阵 }AdjMaxix; 概要设计: 算法主题思想描述: Dijkstra算法的本质是贪心(Greedy)算法～人的本性是贪心的～贪心往往是得不到最好的结果的～但是对于最短路的Dijkstra算法来说～它总是能够得到最优的结果。 以节点1为起始顶点为例说明dijkstra算法～ <1>、置集合S={2,3,...n}, 数组d(1)=0, d(i)=W1->i(1,i之间存在边) or +无穷大(1.i之间不存在边～程序中为INF) <2>、在S中～令d(j)=min{d(i),i属于S}～令S=S-{j}～若S为空集则算 法结束～否则转到3 <3>、对全部i属于S,如果存在边j->i～那么置d(i)=min{d(i), ～转2 d(j)+Wj->i} 详细设计: 在main()函数中读入数据, 通过shift()函数实现对输入数据的邻接矩阵做适当的修改 调用Dijkstra()函数实现求解 调试分析: 此次调试的过程中～出现了没有对Dijkstra算法中的标记数组b[]赋初值的情况导致调试了很久都没有出现正确的结果:悲剧: 测试结果: 用户使用说明: 由于算法自身的限制～Dijkstra算法自身不适用在边权为负的有向图中:另外～本程序只支持1000以内顶点数内的操作。 ,，，代码:详见 code 11.cpp #include using namespace std; #define Max 1001 #define INF 10000001 int adj[Max][Max],dis[Max]; void shift(int n) { for(int i=0;itt) dis[j]=tt; } } if(b[t]) return ; } int main() { int n; cin>>n; for(int i=0;i>adj[i][j]; shift(n); int s,t; cout<<"起点:";cin>>s; cout<<"终点:";cin>>t; Dijkstra(n,s,t); cout<