Re: [閒聊] 每日leetcode已回收
昨天發懶了 對不起:(
要注意k要擺最外層，不然會錯
Bellman-Ford、Floyd-Warshall、Dijkstra 是三種著名的圖論演算法，用於解決最短路
徑問題。這些演算法在使用的場合和特點上有所不同：
### 1. Bellman-Ford 演算法
**特點**：
- 可以處理包含負權重邊的圖。
- 能夠檢測圖中是否存在負權重循環。
- 時間複雜度為 \(O(V \times E)\)，其中 \(V\) 是頂點數，\(E\) 是邊數。
**用途**：
- 適用於邊數不多，且可能有負權重的圖。
- 用於檢測圖中是否存在負權重循環。
**工作原理**：
- 對於每條邊，重複更新最短路徑估計值，最多 \(V-1\) 次，因為最短路徑最多包含
\(V-1\) 條邊。
- 第 \(V\) 次更新後，如果最短路徑估計值還在變化，則存在負權重循環。
### 2. Floyd-Warshall 演算法
**特點**：
- 可以解決所有頂點對之間的最短路徑問題。
- 適用於稠密圖，因為時間複雜度為 \(O(V^3)\)。
- 可以處理負權重邊，但不能處理負權重循環。
**用途**：
- 用於計算所有頂點對之間的最短路徑。
- 適用於圖較小但比較稠密的情況。
**工作原理**：
- 動態規劃方法：通過逐步允許經過更多的中間頂點來更新最短路徑估計值。
- 最終結果為所有頂點對之間的最短路徑距離。
### 3. Dijkstra 演算法
**特點**：
- 適用於非負權重邊的圖。
- 時間複雜度為 \(O(V^2)\) 或使用優先隊列優化為 \(O(E + V \log V)\)。
- 單源最短路徑算法，即從單一源頂點到其他所有頂點的最短路徑。
**用途**：
- 用於解決邊權重非負的單源最短路徑問題。
- 適用於網絡路由、地圖導航等問題。
**工作原理**：
- 使用優先隊列選擇最短路徑估計值最小的頂點，並更新其鄰接頂點的最短路徑估計值。
- 重複此過程直到所有頂點的最短路徑估計值都確定。
### 總結
- **Bellman-Ford**：適合有負權重的圖，可檢測負權重循環，較慢。
- **Floyd-Warshall**：適合計算所有頂點對間的最短路徑，適用於較小但稠密的圖。
- **Dijkstra**：適合邊權重非負的圖，用於單源最短路徑問題，較快。
def minimumCost(self, source: str, target: str, original: List[str], changed:
List[str], cost: List[int]) -> int:
g = [[10**9 for _ in range(26)] for _ in range(26)]
for i in range(len(original)):
g[ord(original[i])-ord('a')][ord(changed[i])-ord('a')] = min(cost[i],
g[ord(original[i])-ord('a')][ord(changed[i])-ord('a')])
for i in range(26):
g[i][i] = 0
# Floyd-Warshall
for k in range(26):
for i in range(26):
for j in range(26):
if g[i][k] + g[k][j] < g[i][j]:
g[i][j] = g[i][k] + g[k][j]
ans = 0
for i in range(len(source)):
if g[ord(source[i])-ord('a')][ord(target[i])-ord('a')] == 10**9:
print(source[i], target[i])
return -1
else:
ans += g[ord(source[i])-ord('a')][ord(target[i])-ord('a')]
return ans
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722092764.A.87A.html
推
07/27 23:10,
1年前
, 1F
07/27 23:10, 1F
→
07/27 23:55,
1年前
, 2F
07/27 23:55, 2F
討論串 (同標題文章)
完整討論串 (本文為第 578 之 1548 篇)：