图论网络规划(共4页).docx

精选优质文档-倾情为你奉上图论练习汪帆 13 土规1202 1某城市要建立一个消防站，为该市所属的七个区服务，如图所示，问应设在那个区，才能使它至最远区的路径最短。 图5.1.1 城市点线模型图解：分析：要求建立的消防站离最远区的路径最短，即要求出任意两点间最优路径，而后从最优路径中选取最大值中的最小值。具体方法则要运用Warshall-Foryd算法求出该图的路由表，从而根据路由表中的最优路线，寻求V1-V7到每一点的最优路径，并比较各路径中最长路径的大小，择取最小值即为题中之所问。（1），建立权矩阵：A=0 3 inf inf inf inf inf ;3 0 2 inf 1.8 2.5 inf;Inf 2 0 6 2 inf inf ;Inf inf 6 0 3 inf inf ;Inf 1.8 2 3 0 4 inf; Inf 2.5 inf i