求解最短路徑的問題，分為使用BFS和使用迪斯科特拉算法，這兩種算法求解的范圍是有區(qū)別的

• BFS適合求解，邊的權(quán)值都是1的圖中的最短路徑的問題
  圖論 之 BFS
• 迪斯科特拉算法適合求解邊的權(quán)值不一樣的圖，其中，該算法有兩種實現(xiàn)方式，分別適用于兩種情況的圖
  • 稠密圖，使用樸素的Dijkstra算法，其中稠密圖的定義是，邊的數(shù)量級與 $o(n^2)$相當?shù)膱D，樸素的Dijkstra算法的時間復(fù)雜度是$o(n^2)$,其中n是圖的節(jié)點的數(shù)量
  • 稀疏圖，使用堆優(yōu)化的Dijkstra算法，算法的時間復(fù)雜度是$o(mlogm)$其中，m是邊的數(shù)量，如果輸入的稠密圖，那么使用堆優(yōu)化的Dijkstra算法的時間復(fù)雜度是$o(n^{2}logn)$

---

樸素的Dijkstras算法的模版

# 存儲邊的情況
edge = [[float('inf')]*n for n in range(n)]
# dis[i]表示 單源點k到其余節(jié)點i的最短的路徑
dis = [float('inf')]*n 
dis[k] = 0
# 這個done[k] = True不用設(shè)置，后面會依據(jù)這個，把起點彈出
done = [False]*n # done[i]標記是否找到 到達節(jié)點i的最短的路徑while True:x = -1for i,ok in enumerate(done):# 找到在還沒確定最小距離的節(jié)點，該節(jié)點到源點的距離最小if not ok and (x < 0 or dis[i] < dis[x]):x = i# 判斷是否都找到了if x < 0:# 這里就已經(jīng)求解完成了，后續(xù)你可以返回最大值？return dis# 有節(jié)點無法到達if dis[x] == float('inf'):return -1# 設(shè)置標志位，表示節(jié)點x的最小距離已經(jīng)確定done[x] = True# 遍歷當前節(jié)點的所有的鄰居，更新答案for j,d in enumerate(edge[x]):dis[j] = min(dis[j],dis[j]+d)

使用堆優(yōu)化的Dijkstra算法

import heapqclass Solution:def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:# 使用堆優(yōu)化的Dijkstra算法# 使用堆優(yōu)化的話，適用于稀疏圖，所以邊的記錄，我們使用鄰接表edge = [[] for _ in range(n)]for x,y,z in times:edge[x-1].append((y-1,z))dis = [float('inf')]*n dis[k-1] = 0# 入堆的元素是 (dis[x],x)，第一個元素是距離，這也是設(shè)置的優(yōu)先級h = [(0,k-1)]while h:# 出堆dx,x = heapq.heappop(h)# 如果當前的距離大于最小距離，直接過if dx > dis[x]:# 說明之前出過堆continue# 訪問鄰居，不一定是這個鄰接表或者鄰接矩陣，二維表也可以for y,d in edge[x]:# 計算更新值，計算方式按照題目的意思new_dis = dx + d # 只有更優(yōu)的值才能被加入進去if new_dis < dis[y]:dis[y] = new_disheapq.heappush(h,(new_dis,y))mx = max(dis)return mx if mx < float('inf') else -1

題目

743.網(wǎng)絡(luò)延遲時間

743.網(wǎng)絡(luò)延遲時間

思路分析：由于邊的數(shù)量遠遠大于節(jié)點的數(shù)量，所以我們還是考慮使用稠密圖下的樸素的Dijkstra算法，最后返回不是無窮的最大的路徑即可

class Solution:def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:# 區(qū)別于BFS求解的最短距離，這個距離的邊的權(quán)值不一樣# 使用樸素的迪斯科特拉算法# 鄰接矩陣記錄邊的情況edge = [[float('inf')]*(n) for _ in range(n)]# 有向邊for e in times:edge[e[0]-1][e[1]-1] = e[2]dis = [float('inf')]*n # 記錄k到各個節(jié)點的最短距離ans = dis[k-1] = 0done = [False] * n # 記錄節(jié)點的最短距離是否被確定while True:x = -1# 找到最短距離還沒確定，并且節(jié)點k到它的距離是最短的節(jié)點for i,ok in enumerate(done):if not ok and (x<0 or dis[i] < dis[x]):x = i # 如果x<0,表示全部的節(jié)點已經(jīng)全部都訪問過了if x < 0 :return ans# 如果最短的節(jié)點的距離是無窮，說明不可達if dis[x] == float('inf'):return -1# 更新ans = dis[x]done[x] = Truefor y,d in enumerate(edge[x]):dis[y] = min(dis[y],dis[x]+d)

使用堆優(yōu)化的解法

import heapqclass Solution:def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:# 使用堆優(yōu)化的Dijkstra算法# 使用堆優(yōu)化的話，適用于稀疏圖，所以邊的記錄，我們使用鄰接表edge = [[] for _ in range(n)]for x,y,z in times:edge[x-1].append((y-1,z))dis = [float('inf')]*n dis[k-1] = 0# 入堆的元素是 (dis[x],x)h = [(0,k-1)]while h:dx,x = heapq.heappop(h)if dx > dis[x]:# 說明之前出過堆continuefor y,d in edge[x]:new_dis = dx + d if new_dis < dis[y]:dis[y] = new_disheapq.heappush(h,(new_dis,y))mx = max(dis)return mx if mx < float('inf') else -1

3341.到達最后一個房間的最少時間I

3341.到達最后一個房間的最少時間I

思路分析：開始的時候，我錯誤的以為題目中只能向右或者向下運動， 所以寫了一個動態(tài)規(guī)劃進行求解，實際上，這個思路是錯誤的,不過要是只能向下或者向右運動的話，動態(tài)規(guī)劃也是一種很好的做法

# 動態(tài)規(guī)劃的做法，竟然可以過700個測試用例
import heapq
class Solution:def minTimeToReach(self, moveTime: List[List[int]]) -> int:# 開始的時候從(0,0)出發(fā)，移動到相鄰的房間，其實也只是向下或向右運動# 感覺可以用動態(tài)規(guī)劃，dp[i][j]表示到達i,j所需的最少的時間# 遞推公式，# dp[i][j] = min(max(dp[i-1][j],moveTime[i][j])+1,max(dp[i][j-1],moveTime[i][j])+1)n = len(moveTime)m = len(moveTime[0])dp = [[float('inf')]*(m+1) for _ in range(n+1)]dp[1][1] = 0for i in range(n):for j in range(m):if i == 0 and j == 0:continuedp[i+1][j+1] = min(max(dp[i][j+1],moveTime[i][j])+1,max(dp[i+1][j],moveTime[i][j])+1)for i in dp:print(i )return dp[n][m]

正確的思路：應(yīng)該是使用Dijkstra算法，不過開始的時候，我有點糾結(jié)這個edge也就是邊的矩陣如何轉(zhuǎn)化為鄰接矩陣或者鄰接表，后面一想，還是我的固定思維阻礙了我，鄰接矩陣和鄰接表只是一個工具，幫助我們找到當前的節(jié)點的鄰居，但是在現(xiàn)在的圖中，你通過坐標的加減不就可以得到對應(yīng)的鄰居嘛！

• 展示使用樸素Dijkstra算法做法

import heapq
class Solution:def minTimeToReach(self, moveTime: List[List[int]]) -> int:# 首先先使用 堆優(yōu)化的Dijkstra進行解題# 圖已經(jīng)構(gòu)建，就是moveTime# dis[i][j]表示(0,0)到(i,j)的最短的時間n,m = len(moveTime),len(moveTime[0])dis = [[float('inf')]*m for _ in range(n)]dis[0][0] = 0done = [[False]*m for _ in range(n)]while True:x,y = -1,-1# 開始遍歷還沒確定的點for i in range(n):for j in range(m):if not done[i][j] and ((x<0 and y <0) or dis[i][j] < dis[x][y]):x,y = i,jif x<0 and y <0:# 說明都找到了return dis[n-1][m-1]# 設(shè)置已經(jīng)找到done[x][y] = True# 訪問鄰居for i,j in (x+1,y),(x-1,y),(x,y+1),(x,y-1):if 0<= i < n and 0<= j < m:dis[i][j] = min(max(dis[x][y],moveTime[i][j]) + 1,dis[i][j])

• 展示使用堆優(yōu)化的Dijkstra算法

import heapq
class Solution:def minTimeToReach(self, moveTime: List[List[int]]) -> int:# 首先先使用 堆優(yōu)化的Dijkstra進行解題# 圖已經(jīng)構(gòu)建，就是moveTime# dis[i][j]表示(0,0)到(i,j)的最短的時間n,m = len(moveTime),len(moveTime[0])dis = [[float('inf')]*m for _ in range(n)]dis[0][0] = 0h = [(0,0,0)]while True:d,x,y = heapq.heappop(h)if x == n-1 and y == m-1:return d # 已經(jīng)更新過了if d > dis[x][y]:continue# 訪問鄰居：for i,j in (x+1,y),(x-1,y),(x,y+1),(x,y-1):if 0<= i <n and 0<= j < m:# 合法的坐標# 計算當前的距離，小于才入堆new_dis = max(d,moveTime[i][j])+1if dis[i][j]>new_dis:dis[i][j] = new_disheapq.heappush(h,(dis[i][j],i,j))