資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學計算機網路中的最短路徑路由是什麼？
在此演算法中，為了選擇路由，演算法會發現兩個節點之間的最短路徑。它可以使用多個跳點、以公里為單位的地理區域或弧的標記來測量路徑長度。
弧的標記可以使用平均排隊時間、標準測試資料包的小時傳輸延遲，或者計算為頻寬、平均距離流量、通訊成本、平均佇列長度、測量延遲或其他因素的函式。
在最短路徑路由中，拓撲通訊網路使用有向加權圖來定義。圖中的節點定義交換元件，圖中的有向弧定義交換元件之間的通訊連線。每個弧都有一個權重，該權重定義了在特定方向上兩個節點之間共享資料包的成本。
此成本通常是一個正值，可以表示延遲、吞吐量、錯誤率、財務成本等因素。兩個節點之間的路徑可以經過各種中間節點和弧。最短路徑路由的目標是在兩個節點之間找到總成本最低的路徑，其中路徑的總成本是該路徑中弧成本的總和。
例如，Dijkstra 演算法使用節點與其沿已知最佳路徑到源節點的距離的標記。最初，所有節點都標記為無窮大，隨著演算法的進行，標記可能會發生變化。標記圖顯示在圖中。
可以按如下方式進行多次傳遞，其中 A 為源節點。
第1次傳遞：B (2, A), C(∞,−), F(∞,−), e(∞,−), d(∞,−), G 60
第2次傳遞：B (2, A), C(4, B), D(5, B), E(4, B), F(∞,−),G(∞,−)
第3次傳遞：B(2, A), C(4, B), D(5, B), E(4, B), F(7, C), G(9, D)
我們可以看到 A 和 G 之間可以有兩條路徑。一條路徑經過 ABCFG，另一條路徑經過 ABDG。第一條路徑長度為 11，第二條路徑長度為 9。因此，選擇第二條路徑，即 G (9, D)。類似地，節點 D 從 A 出發也有三條路徑 ABD、ABCD 和 ABED。第一條路徑長度為 5，其餘兩條路徑長度為 6。因此，選擇第一條路徑。
在多次傳遞中搜索所有節點，最終，將具有最短路徑長度的路由設為永久性，並將路徑的節點用作下一輪的工作節點。
30K+ 瀏覽量
