??前言??

給出幾個點的名稱,在給出幾個點的路徑權重（簡稱路權）就可以計算一個地圖中最短的路權
是不是感覺很神奇。當然啦博主也覺得很神奇，因為博主比較笨嘛,如果只有幾個點的圖集的話
還可以口算出來圖中的最短路,如果有上千個點的話,博主的大腦就不夠用了。所以呢咱們掌握最
短路算法還是必須的,至少可以減少我們的腦力勞動嘛。

??前置知識??

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

十字鏈表：是有向圖存儲的一種鏈式存儲結構,可以看成是有向圖的鄰接表和逆鄰接表合起來得到的鏈表。用十字鏈表來存儲有向圖，可以達到高效的存取效果。同時，代碼的可讀性也會得到提升。

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

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

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

知識介紹到此,下面上練習題吧??

練習題

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

??問題描述??

Problem Description
某省自從實行了很多年的暢通工程計劃后，終于修建了很多路。不過路多了也不好，每次要從一個城鎮(zhèn)到另一個城鎮(zhèn)時，
都有許多種道路方案可以選擇，而某些方案要比另一些方案行走的距離要短很多。這讓行人很困擾。
現(xiàn)在，已知起點和終點，請你計算出要從起點到終點，最短需要行走多少距離。
Input
本題目包含多組數(shù)據(jù)，請?zhí)幚淼轿募Y束。
每組數(shù)據(jù)第一行包含兩個正整數(shù)N和M(0<N<200,0<M<1000)，分別代表現(xiàn)有城鎮(zhèn)的數(shù)目和已修建的道路的數(shù)目。城鎮(zhèn)分別以0～N-1編號。
接下來是M行道路信息。每一行有三個整數(shù)A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城鎮(zhèn)A和城鎮(zhèn)B之間有一條長度為X的雙向道路。
再接下一行有兩個整數(shù)S,T(0<=S,T<N)，分別代表起點和終點。
Output
對于每組數(shù)據(jù)，請在一行里輸出最短需要行走的距離。如果不存在從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)過觀察路的邊權均是正的,所以我們暫定使用迪杰斯特拉算法
回顧一下迪杰斯特拉算法的模板步驟：

① 設置一個最短距離數(shù)組dis（存儲某點到任一點的最短距離）
一個父節(jié)點數(shù)組pre（最短距離訪問該節(jié)點需要首先訪問的那個節(jié)點）
一個標記某點是否找到了最短路的列表visit
一個圖（可以使用鄰接多重表將邊初始化進圖G）
② 將出發(fā)點初始化一下
③ 選出沒有被確定最短路的點中，距離源點最近的點
④ 使用他的邊集優(yōu)化邊中點的最短距離
⑤ 將該點加入已找到最短路的數(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是起點e是終點
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】最短路徑??

??問題描述??

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

??問題分析??

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

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

def spfa(n):
    # 存儲修改過最短路權的點
    t=[]
    t.append(n)
    visit[n]=1
    while t:
        # 每次獲取一個更新過路權的點
        temp=t.pop()
        # 更新與他相連點的路權
        for i in G[temp]:
            if dis[i[0]]>dis[temp]+i[1]:
                dis[i[0]]=dis[temp]+i[1]
                # 被更新過點所連得點也需要更新,所以將該點加入臨時隊列
                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)

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

??問題描述??

給出n個點和m條邊，接著是m條邊，代表從牛a到牛b需要花費c時間，現(xiàn)在所有牛要到牛x那里去參加聚會，
并且所有牛參加聚會后還要回來，給你牛x，除了牛x之外的牛，他們都有一個參加聚會并且回來的最短時間，
從這些最短時間里找出一個最大值輸出
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(用于存儲邊權) P(用于存儲父節(jié)點或者說用于存儲先驅節(jié)點)
② 三層循環(huán),判斷兩點之間最短路是否需要加邊
得到的最短路放在G列表中
得到的最短路路徑放在P數(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))

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

最新評論