在靜態路由選擇算法中，最短路由選擇(Shotest Routing) 算法是一種簡單易懂而套用廣泛的技術。它的基本思想是：建立一個子網圖，圖中每一個節點代表一台路由器，每條弧線代表一條通信線路（鏈路），弧上的數字代表該線路的權重。為了在一對給定的路由器之間選擇一條路由路徑，路由算法只需在圖中找到這對節點之間的最短路徑即可。對於路徑長度測量有多種方法，一種方法是計算站點數量，另外也可以計算距離、信道頻寬、平均通信量、通信開銷、佇列長度、傳播時延等。
基本介紹
- 中文名：最短路由選擇算法
- 典型算法：Dijkstra算法
計算圖中兩個節點之間的最短距離有多種算法，其中最著名的算法是Dijkstra在1959年提出的Dijkstra算法。該算法要求每個節點用從源節點沿已知最佳路逕到本節點的距離來標註。開始時由於一條路徑也不知道，故所有的節點都標註無窮大。隨著算法的進行和不斷找到的路徑，標註隨之改變，使之反映出較好的路徑。一個標註可以是暫時性的(可更改的)，所有標註最初都是暫時的，但一旦發現了標註代表了從源節點到該節點的最短可能路徑時，就使之成為永久性的，不再進行修改。
為了說明加標註算法是怎樣工作的，請參考右圖，其中數字表示兩節點的距離。要找A至D的最短距離，首先A標註為永久性的(用實心圓點表示)作為開始，然後依次考察與A相鄰的每個節點，用他們各自到A的距離重新標註這些點。找到B節點為最短路徑節點後使其成為永久節點，接下來從節點B開始，檢查所有與B相鄰的節點，如果B的標註與從B到所有節點距離之和小於此節點的標註，就重新標註這個節點。
標註算法說明圖
標註算法說明圖