一个难度高的算法问题,是数据结构上的题目,高手帮忙!!(200分)

W

wishme1

Unregistered / Unconfirmed
GUEST, unregistred user!
起点A到B、C、D、E四点的距离和方法依次如下:
A到B点有直接的通路,为10米
A到C点没有直接通路,(1)、从B转为:A到B为10米,B到C为50米,共60米
(2)、从D转为:A到D为30米,D到C为20米,共50米
A到D点有直接的通路,为30米
A到E点有直接的通路,为100米,也可以通过D转,A到D为30米,D到E为60米,共90米
根据迪杰斯特拉(Dijkstra)提出的按路径长度递增的次序产生最短路径的算法,可
得到下表:
A到各点最短距离的推导过程如下:(每轮比较得到的最短可做为下轮通路)
B 10(A,B)
C 无直通 60(A,B,C) 50(A,D,C)
D 30(A,D) 30(A,D)
E 100(A,E) 100(A,E) 90(A,D,E) 90(A,D,E)

最短 B D C E
这样就求出了从A到各点的最短距离
谁能帮我把上面的算法写成程序呢?最好能优化的,因为点可能非常多,要考虑效率
 
用图的遍历是比较规范的做法,针对这样的具体问题,也可以用一个二维数组,存放点到点之间的
直通距离,如果无法直达,可以用负数表示,对数组 做循环,可以求出每一点到其他点的最短距离
 
顶部