精选优质文档-倾情为你奉上19. 利用Matlab编程计算最短路径及中位点选址1、最短路问题两个指定顶点之间的最短路径。例如,给出了一个连接若干个城镇的铁路网络,在这个网络的两个指定城镇间,找一条最短铁路线。以各城镇为图的顶点,两城镇间的直通铁路为图相应两顶点间的边,得图。对的每一边,赋以一个实数直通铁路的长度,称为的权,得到赋权图。的子图的权是指子图的各边的权和。问题就是求赋权图中指定的两个顶点间的具最小权的轨。这条轨叫做间的最短路,它的权叫做间的距离,亦记作。求最短路已有成熟的算法:迪克斯特拉(Dijkstra)算法,其基本思想是按距从近到远为顺序,依次求得到的各顶点的最短路和距离,直至(或直至的所有顶点),算法结束。为避免重复并保留每一步的计算信息,采用了标号算法。下面是该算法。(i) 令,对,令,。(ii) 对每个(),用代替。计算,把达到这个最小值的一个顶点记为,令。(iii). 若,停止;若,用代替,转(ii)。算法结束时,从到各顶点的距离由的最后一次的标号给出。在进入之前的标号叫T标号,进入时的标号叫P标号。算