迪杰斯特拉算法是由荷蘭計(jì)算機(jī)科學(xué)家在1956年發(fā)現(xiàn)的算法稻薇，此算法使用類似廣度優(yōu)先搜索的方法解決了帶權(quán)圖的單源最短路徑問題兔乞。它是一個(gè)貪心算法半夷。
核心思想：
更新鄰接節(jié)點(diǎn)的最短距離
優(yōu)點(diǎn)：
- 解決單個(gè)來源的最短路徑
- 能解決非負(fù)權(quán)的帶權(quán)圖
缺點(diǎn)： - 不能處理帶有負(fù)權(quán)邊的圖(可能得不到最優(yōu)解机杜，認(rèn)為是無法處理負(fù)權(quán)圖)客情，只能處理非負(fù)權(quán)圖其弊。
- 多源無法解決
例題：
力扣743
有 n 個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)癞己，標(biāo)記為 1 到 n。
給你一個(gè)列表 times梭伐，表示信號經(jīng)過 有向 邊的傳遞時(shí)間痹雅。 times[i] = (ui, vi, wi)，其中 ui 是源節(jié)點(diǎn)糊识，vi 是目標(biāo)節(jié)點(diǎn)绩社， wi 是一個(gè)信號從源節(jié)點(diǎn)傳遞到目標(biāo)節(jié)點(diǎn)的時(shí)間。
現(xiàn)在赂苗，從某個(gè)節(jié)點(diǎn) K 發(fā)出一個(gè)信號愉耙。需要多久才能使所有節(jié)點(diǎn)都收到信號？如果不能使所有節(jié)點(diǎn)收到信號哑梳，返回 -1 劲阎。
輸入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
輸出：2
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
g = [[float('inf')] * n for _ in range(n)] # 初始化一個(gè)鄰接矩陣
for x, y, time in times: # 把權(quán)加入矩陣
g[x - 1][y - 1] = time
dist = [float('inf')] * n # 初始化源點(diǎn)到所有點(diǎn)的距離為正無窮
dist[k - 1] = 0 # 源點(diǎn)到自身的距離為0
used = [False] * n # 被使用的點(diǎn)的矩陣
for _ in range(n):
x = -1 # x = -1 是為了初始化, 這個(gè)初始實(shí)際上可以為任何值
# 循環(huán)執(zhí)行完找到當(dāng)前最小的dist
for y, u in enumerate(used):
if not u and (x == -1 or dist[y] < dist[x]):
x = y
used[x] = True
for y, time in enumerate(g[x]): # 更新當(dāng)前階段 源點(diǎn)到 y的最小距離
dist[y] = min(dist[x]+time, dist[y])
ans = max(dist)
return ans if ans < float('inf') else -1
