??前言??

給出幾個(gè)點(diǎn)的名稱,在給出幾個(gè)點(diǎn)的路徑權(quán)重（簡稱路權(quán)）就可以計(jì)算一個(gè)地圖中最短的路權(quán)
是不是感覺很神奇。當(dāng)然啦博主也覺得很神奇，因?yàn)椴┲鞅容^笨嘛,如果只有幾個(gè)點(diǎn)的圖集的話
還可以口算出來圖中的最短路,如果有上千個(gè)點(diǎn)的話,博主的大腦就不夠用了。所以呢咱們掌握最
短路算法還是必須的,至少可以減少我們的腦力勞動(dòng)嘛。

??前置知識(shí)??

圖的話可以大致分為有向圖與無向圖、圖中的邊有的是正權(quán)值,有的是負(fù)權(quán)值
有的是兩點(diǎn)之間多條路,有的甚至有自環(huán)（可以說是灰常的靈活）
創(chuàng)建一個(gè)圖可以用的數(shù)據(jù)結(jié)構(gòu)有：
十字鏈表、鄰接多重表、鄰接矩陣、邊集數(shù)組、鄰接表
本篇博客前兩題解題方法使用的是鄰接表,最后一個(gè)使用的是鄰接矩陣
大家根據(jù)自己的喜好進(jìn)行選擇即可,但是思想還是一樣的
如果大家對(duì)最短路不是很熟的話,推薦大家去看看這個(gè)UP主的視頻,感覺講的賊好傳送門已就緒

十字鏈表：是有向圖存儲(chǔ)的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),可以看成是有向圖的鄰接表和逆鄰接表合起來得到的鏈表。用十字鏈表來存儲(chǔ)有向圖，可以達(dá)到高效的存取效果。同時(shí)，代碼的可讀性也會(huì)得到提升。

鄰接多重表：鄰接多重表是無向圖的一種存儲(chǔ)方式。鄰接多重表是鄰接表的改進(jìn)，它把邊的兩個(gè)頂點(diǎn)存放在邊表結(jié)點(diǎn)中，所有依附于同一個(gè)頂點(diǎn)的邊串聯(lián)在同一鏈表中，由于每條邊依附于兩個(gè)頂點(diǎn)，則每個(gè)邊表結(jié)點(diǎn)同時(shí)鏈接在兩個(gè)鏈表中

鄰接矩陣：是表示頂點(diǎn)之間相鄰關(guān)系的矩陣（個(gè)人感覺也是最簡單的一個(gè),但非常不適合稀疏圖）邏輯結(jié)構(gòu)分為兩部分：V和E集合，其中，V是頂點(diǎn)，E是邊。因此，用一個(gè)一維數(shù)組存放圖中所有頂點(diǎn)數(shù)據(jù)；用一個(gè)二維數(shù)組存放頂點(diǎn)間關(guān)系（邊或弧）的數(shù)據(jù)，這個(gè)二維數(shù)組稱為鄰接矩陣。鄰接矩陣又分為有向圖鄰接矩陣和無向圖鄰接矩陣

邊集數(shù)組：邊集數(shù)組（edgeset array）是利用一維數(shù)組存儲(chǔ)圖中所有邊的一種圖的表示方法。該數(shù)組中所含元素的個(gè)數(shù)要大于等于圖中邊的條數(shù)，每個(gè)元素用來存儲(chǔ)一條邊的起點(diǎn)、終點(diǎn)（對(duì)于無向圖，可選定邊的任一端點(diǎn)為起點(diǎn)或終點(diǎn)）和權(quán)（若有的話），各邊在數(shù)組中的次序可任意安排，也可根據(jù)具體要求而定。

知識(shí)介紹到此,下面上練習(xí)題吧??

練習(xí)題

??【單源最短路&迪杰斯特拉】暢通工程（續(xù)）??

??問題描述??

Problem Description
某省自從實(shí)行了很多年的暢通工程計(jì)劃后，終于修建了很多路。不過路多了也不好，每次要從一個(gè)城鎮(zhèn)到另一個(gè)城鎮(zhèn)時(shí)，
都有許多種道路方案可以選擇，而某些方案要比另一些方案行走的距離要短很多。這讓行人很困擾。
現(xiàn)在，已知起點(diǎn)和終點(diǎn)，請(qǐng)你計(jì)算出要從起點(diǎn)到終點(diǎn)，最短需要行走多少距離。
Input
本題目包含多組數(shù)據(jù)，請(qǐng)?zhí)幚淼轿募Y(jié)束。
每組數(shù)據(jù)第一行包含兩個(gè)正整數(shù)N和M(0<N<200,0<M<1000)，分別代表現(xiàn)有城鎮(zhèn)的數(shù)目和已修建的道路的數(shù)目。城鎮(zhèn)分別以0～N-1編號(hào)。
接下來是M行道路信息。每一行有三個(gè)整數(shù)A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城鎮(zhèn)A和城鎮(zhèn)B之間有一條長度為X的雙向道路。
再接下一行有兩個(gè)整數(shù)S,T(0<=S,T<N)，分別代表起點(diǎn)和終點(diǎn)。
Output
對(duì)于每組數(shù)據(jù)，請(qǐng)?jiān)谝恍欣镙敵鲎疃绦枰凶叩木嚯x。如果不存在從S到T的路線，就輸出-1.
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
2
-1

??問題分析??

本題目中求解的是單源最短路,經(jīng)過觀察路的邊權(quán)均是正的,所以我們暫定使用迪杰斯特拉算法
回顧一下迪杰斯特拉算法的模板步驟：

① 設(shè)置一個(gè)最短距離數(shù)組dis（存儲(chǔ)某點(diǎn)到任一點(diǎn)的最短距離）
一個(gè)父節(jié)點(diǎn)數(shù)組pre（最短距離訪問該節(jié)點(diǎn)需要首先訪問的那個(gè)節(jié)點(diǎn)）
一個(gè)標(biāo)記某點(diǎn)是否找到了最短路的列表visit
一個(gè)圖（可以使用鄰接多重表將邊初始化進(jìn)圖G）
② 將出發(fā)點(diǎn)初始化一下
③ 選出沒有被確定最短路的點(diǎn)中，距離源點(diǎn)最近的點(diǎn)
④ 使用他的邊集優(yōu)化邊中點(diǎn)的最短距離
⑤ 將該點(diǎn)加入已找到最短路的數(shù)組

??代碼實(shí)現(xiàn)??

n,m=map(int,input().split())
visit=[False]*(n+1)
dis=[1e8]*(n+1)
side=[list(map(int,input().split())) for i in range(m)]
G={k:[] for k in range(n)}
# s是起點(diǎn)e是終點(diǎn)
s,e=map(int,input().split())
# 初始化鄰接表
for i in side:
    G[i[0]].append([i[1],i[2]])
    G[i[1]].append([i[0],i[2]])

dis[s]=0
for _ in range(n):
    mi=1e8
    for i in range(1,len(dis)):
        if dis[i]<mi and not visit[i]:
            mi=dis[i]
            s=i
    for i in G[s]:
        if dis[i[0]]>dis[s]+i[1]:
            dis[i[0]]=dis[s]+i[1]
    visit[s]=True
            

print(dis[e])

??【單源最短路 & spfa】最短路徑??

??問題描述??

資源限制
時(shí)間限制：1.0s 內(nèi)存限制：256.0MB
問題描述
給定一個(gè)n個(gè)頂點(diǎn)，m條邊的有向圖（其中某些邊權(quán)可能為負(fù)，但保證沒有負(fù)環(huán)）。請(qǐng)你計(jì)算從1號(hào)點(diǎn)到其他點(diǎn)的最短路（頂點(diǎn)從1到n編號(hào)）。
輸入格式
第一行兩個(gè)整數(shù)n, m。
接下來的m行，每行有三個(gè)整數(shù)u, v, l，表示u到v有一條長度為l的邊。
輸出格式
共n-1行，第i行表示1號(hào)點(diǎn)到i+1號(hào)點(diǎn)的最短路。
樣例輸入
3 3
1 2 -1
2 3 -1
3 1 2
樣例輸出
-1
-2
數(shù)據(jù)規(guī)模與約定
對(duì)于10%的數(shù)據(jù)，n = 2，m = 2。
對(duì)于30%的數(shù)據(jù)，n <= 5，m <= 10。
對(duì)于100%的數(shù)據(jù)，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保證從任意頂點(diǎn)都能到達(dá)其他所有頂點(diǎn)。

??問題分析??

spfa是一種隨機(jī)方法,有些數(shù)據(jù)可能會(huì)將其卡死。他的思想是使用隊(duì)列進(jìn)行算法優(yōu)化
特點(diǎn)是可以求含有負(fù)邊權(quán)圖的最短路。每次將更新過最短長度的點(diǎn)加入隊(duì)列中（因?yàn)樵擖c(diǎn)最短路更新了那么與他相連的點(diǎn)最短路也可能更新）然后從隊(duì)列中每次取出一個(gè)點(diǎn),對(duì)該點(diǎn)所連的點(diǎn)進(jìn)行邊權(quán)更新。然后將更新后的點(diǎn)再加入隊(duì)列中,直到?jīng)]有點(diǎn)更新為止。

??代碼實(shí)現(xiàn)??

def spfa(n):
    # 存儲(chǔ)修改過最短路權(quán)的點(diǎn)
    t=[]
    t.append(n)
    visit[n]=1
    while t:
        # 每次獲取一個(gè)更新過路權(quán)的點(diǎn)
        temp=t.pop()
        # 更新與他相連點(diǎn)的路權(quán)
        for i in G[temp]:
            if dis[i[0]]>dis[temp]+i[1]:
                dis[i[0]]=dis[temp]+i[1]
                # 被更新過點(diǎn)所連得點(diǎn)也需要更新,所以將該點(diǎn)加入臨時(shí)隊(duì)列
                if visit[i[0]]==0:
                    visit[i[0]]=1
                    t.append(i[0])
n,m=map(int,input().split())
ls=[list(map(int,input().split())) for i in range(m)]
G={k:[] for k in range(1,n+1)}
for i in ls:
    G[i[0]].append([i[1],i[2]])
visit=[0]*(n+1)
dis=[1e8]*(n+1)
dis[1]=0
spfa(1)
print(dis)

??【多源最短路 & 弗洛伊德】牛牛聚會(huì)??

??問題描述??

給出n個(gè)點(diǎn)和m條邊，接著是m條邊，代表從牛a到牛b需要花費(fèi)c時(shí)間，現(xiàn)在所有牛要到牛x那里去參加聚會(huì)，
并且所有牛參加聚會(huì)后還要回來，給你牛x，除了牛x之外的牛，他們都有一個(gè)參加聚會(huì)并且回來的最短時(shí)間，
從這些最短時(shí)間里找出一個(gè)最大值輸出
Input
Line 1: Three space-separated integers, respectively: N, M, and X
Lines 2… M+1: Line i+1 describes road i with three space-separated integers:
Ai, Bi, and Ti. The described road runs from farm Ai to farm Bi, requiring Ti time units to traverse.
Output
Line 1: One integer: the maximum of time any one cow must walk.
Examples
Sample Input
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
Sample Output
10

??問題分析??

不妨先回憶一下怎么使用弗洛伊德算法:

① 構(gòu)造兩個(gè)圖G(用于存儲(chǔ)邊權(quán)) P(用于存儲(chǔ)父節(jié)點(diǎn)或者說用于存儲(chǔ)先驅(qū)節(jié)點(diǎn))
② 三層循環(huán),判斷兩點(diǎn)之間最短路是否需要加邊
得到的最短路放在G列表中
得到的最短路路徑放在P數(shù)組中

??代碼實(shí)現(xiàn)??

def F(n):
    for i in range(1,n+1):
        for j in range(1,n+1):
            for k in range(1,n+1):
                if G[i][j]>G[i][k]+G[k][j]:
                    G[i][j]=G[i][k]+G[k][j]
                    P[i][j]=k

n,m,x=map(int,input().split())
G=[[1e7 if i!=j else 0 for i in range(n+1)] for j in range(n+1)]
P=[[-1 if i==j else i  for i in range(n+1)] for j in range(n+1)]
ls=[list(map(int,input().split())) for i in range(m)]
for i in ls:
    G[i[0]][i[1]]=i[2]
F(n)
for i in G:
    print(i)
for i in P:
    print(i)
ans=[]
for i in range(1,n+1):
    if i==x:
        continue
    if G[i][x]!=1e7 and G[x][i]!=1e7:
        ans.append(G[i][x]+G[x][i])
print(ans)
print(max(ans))

到此這篇關(guān)于Python 最短路徑的幾種求解方式的文章就介紹到這了,更多相關(guān)Python 最短路徑 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論