明天就要面試了我也太緊張了吧

但是終于找到了一個比較好理解的dijkstra的python解法，讓我快點把它背下來！?。。?/p>

題目

先把題目放出來

某通信網(wǎng)絡中有N個網(wǎng)絡結(jié)點，用1到N進行標識。網(wǎng)絡通過一個有向無環(huán)圖表示，其中題的邊的值表示結(jié)點之間的消息傳遞時延。現(xiàn)給定相連節(jié)點之間的時延列表 times[i] = {u,v,w},其中u表示源節(jié)點，v表示目的節(jié)點，w表示u和v之間的消息傳遞時延。
請計算給定源結(jié)點到目的結(jié)點的最小傳輸時延，如果目的結(jié)點不可達，返回-1。

輸入描述：
輸入的第一行為兩個正整數(shù)，分別表示網(wǎng)絡結(jié)點的個數(shù)N以及時延列表長度M，用空格分隔。
接下來的M行為兩個結(jié)點間的時延列表[u,v,w]
輸入的最后一行為兩個正整數(shù)，分別表示源結(jié)點和目的結(jié)點。

比如：

一個有向無環(huán)圖，用dfs也很好做。這里我們重點看一下dijkstra怎么做。

dijkstra算法的python實現(xiàn)

最短路徑算法Dijkstra，主要思想是貪心。每次遍歷到始點距離最近且未訪問過的頂點的鄰接節(jié)點，直到擴展到終點為止。
更具體地來說：
假設我們現(xiàn)在在一個有權(quán)圖中，圖中有n個點，點與點相連的路徑上都分配有權(quán)重，代表了兩點之間的距離。現(xiàn)在有一個起始點i，終點j，如果求i到j的最短距離。

1. 我們建立一個集合s，把起始點i放進去，然后在與i相鄰的邊中尋找與i距離最近的點，并把這個點放到集合中去。
2. 然后第二次遍歷與集合中的點相連的點，并更新到起始點的距離，并把距離起始點i最近的點放到集合中去。
3. 繼續(xù)上面的做法，每次都在集合中添加一個點。直到?jīng)]有新的點可以添加進去。

我們來寫一個比較簡單的python實現(xiàn)。
假設現(xiàn)在有n個節(jié)點，同時有一個輸入distance距離列表，里面的元素表示的是[u,v,w]即u到v的距離?，F(xiàn)在給定起點k，求k到最遠的點的最小距離

dist = [float('inf')]*n # 構(gòu)建一個列表存放n個結(jié)點到目標k的距離
dist[k-1] = 0  # 第k個結(jié)點到他本身的距離為0

g = [[float('inf')] * n for _ in range(n)] # 構(gòu)建一個矩陣，表示n個結(jié)點彼此的距離。
for x, y, dis in distance:
	g[x-1][y-1] = time  # 按照distance列表更新矩陣中兩兩結(jié)點的距離。

used = [False]*n # 判斷點是否已經(jīng)加入了set里面。

for _ in range(n):
	x = -1
	for y, u in enumerate(used):
		if not u and (x == -1 or dist[y] < dist[x]): #只考慮沒有使用過的節(jié)點，尋找結(jié)點們到初始點的最小距離。
		# 毫無疑問，在第一次遍歷中，這個距離是0，目標點是我們的源點本身。
			x = y  # 如果距離小，就用新的點替換掉x。
		
	used[x] = True # 每次都使用距離源點最近的點
	for y, time in enumerate(g[x]):
		dist[y] = min(dist[y], dist[x]+time)  # 更新相連的結(jié)點到源點的距離

ans = max(dist)  # 這就是我們要求的k到最遠的點的最小距離

dijkstra的時間復雜度是$O(N^2)$.

這個題也可以用dfs的方法來作，遍歷到父結(jié)點時，更新所有的子結(jié)點到源點的距離。dfs解該題的時間復雜度更高一點，是 $O(N^N)$.
同樣給出一個解法代碼。

map_dict = defaultdict(list)
for u, v, w in distance:
	map_dict[u].append([v,w])  

dist = [float('inf')] * n
def dfs(index, dis):
	if dis < dist[index-1]:
		dist[index-1] = dis
		for v, w in map_dict[index]:
			dfs(v,dis+w)
dfs(k,0)

res = max(dist)

python解答

我們回到題目的python解答上。

dfs解法

首先我們給出一個dfs的解答。
可以看到這個解法和上面的dfs幾乎一模一樣，區(qū)別是這里返回的是源節(jié)點到目標點的距離。

def solution(times,src, dist):
    graph = {}
    for u,v, w in times:
        if u not in graph:
            graph[u] = []
        graph[u].append([v,w])
    
    root = [float('inf')]*N    
    def dfs(index, dis):
        
        if dis<root[index-1]:
            root[index-1] = dis
            if index in graph:
                for u, v in graph[index]:
                    dfs(u,dis+v)
                
    dfs(src,0)
    res = root[dist-1]
    return res if res!=float('inf') else -1
    

dijkstra解法

這個解法也是和上面的思路一樣，只不過在發(fā)現(xiàn)x==dis-1的時候，提前break結(jié)束了這個循環(huán)。文章來源地址http://www.zghlxwxcb.cn/news/detail-614754.html

def solution(times, src, dis):
    g = [[float('inf')]*N for _ in range(N)]
    for u,v, time in times:
        g[u-1][v-1] = time
        
    dist = [float('inf')]*N
    dist[src-1] = 0
    used = [False]*N
    for i in range(N):
        x = -1
        for y, u in enumerate(used):
            if not u and (x==-1 or dist[y]< dist[x]):
                x = y
        if x == dis-1:
            break
        used[x] = True
        for y, time in enumerate(g[x]):
            dist[y] = min(dist[y],dist[x]+time)
            
    return dist[dis-1]

到了這里，關(guān)于[華為OD] 最小傳輸時延(dijkstra算法)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！