b****d
发帖数: 1311 | 1
数据结构课里学过最短路径的求法。把所有地点看作一个个点。两点间若有线路连结，
则以线段相连，线段长度为两点之距离。设起点S，终点D。除S外，每个和S相连的点
都对应一个数字和一个点，具体做法是：
设A0=B0={S}，首先，把和B0中相邻的点P对应上(d(P),S)，d(P)是P到S的距离。
如果我们已经有A(k-1)和B(k-1)，令Ak是和B(k-1)相邻的所有点。Bk是Ak中去除B1,
B2,...,B(k-1)的点。对Ak中的每个点Q，寻找B(k-1)中和Ak相邻的点R，使得R和Q的
距离加上d(R)的值最小，以此值作为d(Q), Q点对应上(d(Q),R)。如此类推直到某个
B(n)为空集为止。 |
|
