货担郎问题.txt

货担郎问题

/////////////////////////////货担郎问题////////////////////////////


求从顶点v到其他顶点的最短路径的Dijkstra算法为

｛
初始化图的邻接矩阵Edge[][]；
为各顶点设置距离，记i顶点到顶点v的距离为dist[i];
让集合S只含有v；
for（i=0;i<n-1;i++）
 {
	在V-S中选择一个顶点u，使dist[u]为可选的最短；
	将顶点u加入到集合S中；
	对于每个属于V-S的顶点w，且w与u邻接，调整v到w的距离；
	if（dist[w]>dist[u]+Edge[u][v]）
		dist[w]=dist[u]+Edge[u][w]
 }

｝

在path[]数组中存放最短路径上某节点的前驱节点，利用递归可求解由源节点到任一节点的具体路径。


在给出的图中，若从V0出发，则按下列方法初始化图的邻接矩阵

::::::::::::::::::::::::::::从V0出发::::::::::::::::::::::::::::
顶点编号	0	1	2	3	4	5
顶点名称	V0	V1	V2	V3	V4	V5
邻接矩阵
+-                      -+
|  0   M  10   M  30 100 |  
|  M   0   5   M   M   M |
| 10   5   0  50   M   M | 
|  M   M  50   0  20  10 |
| 30   M   M  20   0  60 |
|100   M   M  10  60   0 |
+-                      -+

所得结果为：
distance from vertice No.0 is:
0 15 10 50 30 90（V0到V0,V1，V2，V3，V4，V5的距离）
从V0到V1：0->2->(即V0->V2->V1)
从V0到V2：0->（即V0->V2）
从V0到V3：0->4->（即V0->V4->V3）
从V0到V4：0->（即V0->V4）
从V0到V5：0->4->（即V0->V4->V5）


::::::::::::::::::::::::::::从V1出发::::::::::::::::::::::::::::
顶点编号	0	1	2	3	4	5
顶点名称	V1	V0	V2	V3	V4	V5
邻接矩阵
+-                      -+
|  0   M   5   M   M   M |  
|  M   0  10   M  30 100 |
|  5  10   0  50   M   M | 
|  M   M  50   0  20  10 |
|  M  30   M  20   0  60 |
|  M 100   M  10  60   0 |
+-                      -+
从V1到V0：0->2->(即V1->V2->V0)
从V1到V2：0->（即V1->V2）
从V1到V3：0->2->（即V1->V2->V3）
从V1到V4：0->2->1->（即V1->V2->V0->V4）
从V1到V5：0->2->3->（即V1->V2->V3->V5）

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
同理，出发顶点为第i个顶点，就将图邻接矩阵中，第0行与第i行交换，第0列与第i列交换，所得结果打印的为顶点编号，换算成顶点名称即可。