dijkstra求最短路径.txt

用Dijkstra算法求解最短路径

格式说明：
1，输入顶点数及边数用，分开
2，输入各条边的权值时也使用，分开，输完一条边摁回车键
3，停止求最短路径输入0即可，输入的源结点超出范围也会自动退出

数据测试：
第一组：
输入图中顶点个数和边数n,e:  3,3
输入3条边的i,j及w:
1,2,6
1,3,5
2,1,9
有向图的存储结构建立完毕！

输入源点v: 1
从源点v1到其他结点的最短距离及路径为：
路径长度    路径
    0     v1
    6     v2<-v1
    5     v3<-v1

输入源点v: 2
从源点v2到其他结点的最短距离及路径为：
路径长度    路径
    9     v1<-v2
    0     v2
   14     v3<-v1<-v2

输入源点v: 3
从源点v3到其他结点的最短距离及路径为：
路径长度    路径
32767     v3
32767     v3
    0     v3

输入源点v: 4
从源点v4到其他结点的最短距离及路径为：
Press any key to continue


第二组：
输入图中顶点个数和边数n,e:  5,7
输入7条边的i,j及w:
1,2,10
1,3,3
1,4,20
2,4,5
3,2,2
3,5,15
4,5,9
有向图的存储结构建立完毕！

输入源点v: 1
从源点v1到其他结点的最短距离及路径为：
路径长度    路径
    0     v1
    5     v2<-v3<-v1
    3     v3<-v1
   10     v4<-v2<-v3<-v1
   18     v5<-v3<-v1

输入源点v: 2
从源点v2到其他结点的最短距离及路径为：
路径长度    路径
32767     v1
    0     v2
32767     v3
    5     v4<-v2
   14     v5<-v4<-v2

输入源点v: 3
从源点v3到其他结点的最短距离及路径为：
路径长度    路径
32767     v1
    2     v2<-v3
    0     v3
    7     v4<-v2<-v3
   15     v5<-v3

输入源点v: 4
从源点v4到其他结点的最短距离及路径为：
路径长度    路径
32767     v1
32767     v2
32767     v3
    0     v4
    9     v5<-v4

输入源点v: 5
从源点v5到其他结点的最短距离及路径为：
路径长度    路径
32767     v5
32767     v5
32767     v5
32767     v5
    0     v5

输入源点v: 0
从源点v0到其他结点的最短距离及路径为：
Press any key to continue