資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學計算機網路中的最短路徑演算法
在計算機網路中，最短路徑演算法旨在找到網路節點之間的最優路徑，以最大限度地降低路由成本。它們是圖論中提出的最短路徑演算法的直接應用。
解釋
假設一個網路由N個頂點（節點或網路裝置）組成，這些頂點透過M條邊（傳輸線路）連線。每條邊都與一個權重相關聯，表示傳輸線路的物理距離或傳輸延遲。最短路徑演算法的目標是在沿邊的任何一對頂點之間找到一條路徑，使邊的權重之和最小。如果邊的權重相等，則最短路徑演算法旨在找到具有最小跳數的路徑。
常見的最短路徑演算法
一些常見的最短路徑演算法包括：
Bellman-Ford演算法
Dijkstra演算法
Floyd-Warshall演算法
以下部分將描述每種演算法。
Bellman-Ford演算法
輸入 - 表示網路的圖；以及一個源節點 s
輸出 - 從 s 到所有其他節點的最短路徑。
將從 s 到所有節點的距離初始化為無窮大 (∞)；到自身的距離為 0；一個大小為 |V|（節點數）的陣列 dist[]，所有值都為 ∞，除了 dist[s]。
迭代計算最短距離。對除 s 之外的每個節點重複 |V|- 1 次：
對連線頂點 u 和 v 的每條邊重複：
如果 dist[v] > (dist[u] + 邊 u-v 的權重)，則
更新 dist[v] = dist[u] + 邊 u-v 的權重
陣列 dist[] 包含從 s 到每個其他節點的最短路徑。
Dijkstra演算法
輸入 - 表示網路的圖；以及一個源節點 s
輸出 - 以 s 為根節點的最短路徑樹 spt[]。
初始化：
一個大小為 |V|（節點數）的距離陣列 dist[]，其中 dist[s] = 0 且 dist[u] = ∞（無窮大），其中 u 表示圖中除 s 之外的節點。
一個數組 Q，包含圖中的所有節點。當演算法執行完成時，Q 將變為空。
一個空集 S，將訪問過的節點新增到其中。當演算法執行完成時，S 將包含圖中的所有節點。
當 Q 不為空時重複：
從 Q 中移除具有最小 dist[u] 且不在 S 中的節點 u。在第一次執行中，移除 dist[s]。
將 u 新增到 S 中，標記 u 為已訪問。
對於每個與 u 相鄰的節點 v，更新 dist[v] 為：
如果 (dist[u] + 邊 u-v 的權重) < dist[v]，則
更新 dist[v] = dist[u] + 邊 u-v 的權重
陣列 dist[] 包含從 s 到每個其他節點的最短路徑。
Floyd-Warshall演算法
輸入 - 一個成本鄰接矩陣 adj[][]，表示網路中節點之間的路徑。
輸出 - 一個最短路徑成本矩陣 cost[][]，以成本表示圖中每對節點之間的最短路徑。
如下填充 cost[][]
如果 adj[][] 為空，則 cost[][] = ∞（無窮大）
否則 cost[][] = adj[][]
N = |V|，其中 V 表示網路中的節點集。
對於 k = 1 到 N 重複：
對於 i = 1 到 N 重複：
對於 j = 1 到 N 重複：
如果 cost[i][k] + cost[k][j] < cost[i][j]，則
更新 cost[i][j] := cost[i][k] + cost[k][j]
矩陣 cost[][] 包含從每個節點 i 到每個其他節點 j 的最短成本。
48K+ 次瀏覽
