1、最短路問題 兩個指定頂點之間的最短路徑。 例如，給出了一個連線若干個城鎮的鐵路網路，在這個網路的兩個指定城鎮間，找一條最短鐵路線。 以各城鎮為圖G的頂點，兩城鎮間的直通鐵路為圖G相應兩頂點間的邊，得圖G。對G的每一邊e，賦以一個實數)(ew—直通鐵路的長度，稱為e的權，得到賦權圖G。G的子圖的權是指子圖的各邊的權和。問題就是求賦權圖G中指定的兩個頂點00,vu間的具最小權的軌。這條軌叫做00,vu間的最短路，它的權叫做00,vu間的距離，亦記作),(00vud。 求最短路已有成熟的演算法：迪克斯特拉（Dijkstra）演算法，其基本思想是按距0u從近到遠為順序，依次求得0u到G的各頂點的最短路和距離，直至0v（或直至G的所有頂點），演算法結束。為避免重複並保留每一步的計算資訊，採用了標號演算法。下面是該演算法。 (i) 令0)(0ul，對0uv，令)(vl，}{00uS，0i。 (ii) 對每個iSv（iiSVS），用 )} ()(),({minuvwulvli Su 代替)(vl。計算)}({minvli Sv，把達到這個最小值的一個頂點記為1iu，令 《計量地理學》（徐建華，高等教育出版社，2005）配套實習指導 140 }{11iiiuSS。 (iii). 若1||Vi，停止；若1||Vi，用1i代替i，轉(ii)。 演算法結束時，從0u到各頂點v的距離由v的最後一次的標號)(vl給出。在v進入iS之前的標號)(vl叫T標號，v進入iS時的標號)(vl叫P標號。演算法就是不斷修改各項點的T標號，直至獲得P標號。若在演算法執行過程中，將每一頂點獲得P標號所由來的邊在圖上標明，則演算法結束時，0u至各項點的最短路也在圖上標示出來了。 2、選址問題－以中位點選址為例 中位點選址問題的質量判據為：使最佳選址為止所在的定點到網路圖中其他頂點的最短路徑距離的總和（或者以各個頂點的載荷加權求和）達到最小。
1、最短路問題 兩個指定頂點之間的最短路徑。 例如，給出了一個連線若干個城鎮的鐵路網路，在這個網路的兩個指定城鎮間，找一條最短鐵路線。 以各城鎮為圖G的頂點，兩城鎮間的直通鐵路為圖G相應兩頂點間的邊，得圖G。對G的每一邊e，賦以一個實數)(ew—直通鐵路的長度，稱為e的權，得到賦權圖G。G的子圖的權是指子圖的各邊的權和。問題就是求賦權圖G中指定的兩個頂點00,vu間的具最小權的軌。這條軌叫做00,vu間的最短路，它的權叫做00,vu間的距離，亦記作),(00vud。 求最短路已有成熟的演算法：迪克斯特拉（Dijkstra）演算法，其基本思想是按距0u從近到遠為順序，依次求得0u到G的各頂點的最短路和距離，直至0v（或直至G的所有頂點），演算法結束。為避免重複並保留每一步的計算資訊，採用了標號演算法。下面是該演算法。 (i) 令0)(0ul，對0uv，令)(vl，}{00uS，0i。 (ii) 對每個iSv（iiSVS），用 )} ()(),({minuvwulvli Su 代替)(vl。計算)}({minvli Sv，把達到這個最小值的一個頂點記為1iu，令 《計量地理學》（徐建華，高等教育出版社，2005）配套實習指導 140 }{11iiiuSS。 (iii). 若1||Vi，停止；若1||Vi，用1i代替i，轉(ii)。 演算法結束時，從0u到各頂點v的距離由v的最後一次的標號)(vl給出。在v進入iS之前的標號)(vl叫T標號，v進入iS時的標號)(vl叫P標號。演算法就是不斷修改各項點的T標號，直至獲得P標號。若在演算法執行過程中，將每一頂點獲得P標號所由來的邊在圖上標明，則演算法結束時，0u至各項點的最短路也在圖上標示出來了。 2、選址問題－以中位點選址為例 中位點選址問題的質量判據為：使最佳選址為止所在的定點到網路圖中其他頂點的最短路徑距離的總和（或者以各個頂點的載荷加權求和）達到最小。