加權有向圖與dijkstra算法找到最短路徑

加權有向圖的構造

最短路徑問題與最短路徑樹

最短路徑問題（The shortest path problem）定義

• 最短路徑可以是時間花費最短，也可以是距離最短，或是花費最少
• 在圖論中，最短路徑問題指的是一個graph中，想要找到兩個頂點之間的路徑使它們間連通的全部邊的權重和最小化

最短路徑的性質

路徑具有方向性

權重不一定等價于距離。權重可以是距離、時間、花費等內容,權重最小指的是成本最低

只考慮連通圖。一副圖中并不是所有的頂點都是可達的，如果s和t不可達，那么它們之間也就不存在最短路徑，為了簡化問題,這里只考慮連通圖。

最短路徑不一定是唯一的。 從一個頂點到達另外一個頂點的權重最小的路徑可能會有很多條，這里只要找出一條即啊。

使用dijkstra算法找到最短路徑樹

最短路徑樹（Shortest-path tree）定義

• 給定一副加權有向圖和一個頂點s，以s為起點的一棵最短路徑樹是圖的一副子圖，它包含頂點s以及從s可達的所有頂點。這棵有向樹的根結點為s，樹的每條路徑都是有向圖中的一 條最短路徑。
  去往dijkstra算法
  

class DirectedEdge:def __init__(self, _from, _to, weight):self._from = _fromself._to = _toself.weight = weightdef get_weight(self):return self.weightdef start(self):return self._fromdef end(self):return self._to

• 加權有向圖的邊具有方向，其中_from是出發頂點；_to是目的頂點；weight是這條邊的權重。

加權有向圖的實現

去往dijkstra算法

from Structure.graph.DirectedEdge import DirectedEdgeclass WeightedDigraph:def __init__(self, num):self.num_vertices = numself.num_edges = 0self.adj_list = [[] for _ in range(num)]def add_edge(self, edge: DirectedEdge):_from = edge.start()# _to = edge.end()self.adj_list[_from].append(edge)self.num_edges += 1def get_all_edges_of(self, v):"""Get all edges connected with v"""return self.adj_list[v]def get_all_edges(self):"""Get all edges of this graph"""return [e for i in range(self.num_vertices) for e in self.adj_list[i]]

• num_vertices 定義了圖中頂點的個數；num_edges 為邊的數量，初始狀態下各頂點相互分隔，邊數量為0；adj_list 是一個列表，索引代表頂點，每個值也是一個列表，儲存著對應頂點通向的目的頂點；
• add_edge(edge: DirectedEdge)傳入一個DirectedEdge對象，向adj_list中對應位置添加一條有向邊；
• get_all_edges_of(v) 獲取傳入的頂點v的所有通往的邊
• get_all_edges() 獲取整張圖的所有的邊；

松弛方法relax的過程

• 當前已經存在一條最短路徑S->W且知道其路徑總權重SP_weight[w]，現在要判斷下一條路徑S->V->W是否更短，則首先計算S->V的最短路徑的總權重SP_weight[V]，然后再加上V->W的最短邊的權重，如果相加之和大于之前最短路徑的權重和SP_weight[W]，則無需松弛，無需更新數據
  
• 當從起點S到達V的最短路徑的權重之和加上從V到達W的權重小于從起點S到達W的最短路徑權重之和時，則對應松弛成功的情況，需要將從S到W的最短路徑權重之和SP_weight[W]更新為SP_weight[V] + [V到W邊的權重]，到達終點前的最后一條邊last_edge要更新為[V→W]
• 頂點的松弛是基于邊的松弛完成的，只需要把某個頂點指出的所有邊松弛,那么該頂點就松弛完畢。例如要松弛頂點v，只需要遍歷v的鄰接表，把每一邊都松弛，那么頂點v就松弛了。

Python代碼實現dijkstra算法尋找最短路徑

from Structure.graph.DirectedEdge import DirectedEdge from Structure.graph.WeightedDigraph import WeightedDigraph from Structure.PriorityQueue.IndexMinPriorityQueue import IndexMinPriorityQueue from math import infclass DijkstraSP:def __init__(self, graph, start_vertex=0):self.graph = graphself.start_vertex = start_vertex# Each vertex(index) point to a minimum weight from the start vertex(0)self.SP_weight = [inf for _ in range(self.graph.num_vertices)]# Store the last SPT edge from 0 to the vertex(index)self.last_edge = [None for _ in range(self.graph.num_vertices)]# Store all edges? of the SPT(all the last_edge)# Index equals to vertex, element equals to edge.weight from the current vertexself.SPT_edge_weights = IndexMinPriorityQueue(self.graph.num_vertices) # num_vertices - 1 + 1self.SP_weight[start_vertex] = 0.0# Index equals to vertex, element equals to weightself.SPT_edge_weights.insert(start_vertex, 0.0)while self.SPT_edge_weights.size() > 0:min_weight_vertex = self.SPT_edge_weights.delete_min_and_get_index()# print(f"min_weight_vertex {min_weight_vertex}")self.relax(min_weight_vertex)def relax(self, v):"""Check if the total weight from 0 to v is lesser than from 0 to w"""# To relax a vertex is to relax all its edgesfor e in self.graph.get_all_edges_of(v):w = e.end()if self.SP_weight[v] + e.weight < self.SP_weight[w]:self.SP_weight[w] = self.SP_weight[v] + e.weightself.last_edge[w] = eif self.SPT_edge_weights.is_index_exist(w):self.SPT_edge_weights.change_item(w, e.weight)else:self.SPT_edge_weights.insert(w, e.weight)def sp_weight_to(self, v):"""Get the total weight of a shortest path from 0 to v"""return self.SP_weight[v]def has_path_to(self, v):"""Check if the start vertex to v is feasible"""# return self.graph.adj_list[v]return self.SP_weight[v] < infdef shortest_path_to(self, v):"""Get all the shortest path edges from 0 to v"""if not self.has_path_to(v):returnall_sp_edges = []while True:e = self.last_edge[v]if not e:breakall_sp_edges.insert(0, e)v = e.start()return all_sp_edges

屬性和方法說明

構造方法__init__()中
graph 接收傳入的圖對象；start_vertex 為要找出最短路徑樹的起始頂點；
SP_weight是一個列表，索引代表當前頂點，值代表從起點出發到索引對應頂點的最短路徑的權重和，它初始化儲存全部為無窮大inf，可以使搜尋時路徑時的初次權重比較一定會成功；
last_edge是一個列表，索引對應著頂點，儲存的值表示從起點到索引對應頂點的最短路徑中的最后一條邊；
SPT_edge_weights是一個最小優先隊列MinIndexPriorityQueue對象，索引代表頂點，存入的值是從起點到當前遍歷頂點的經過松弛relax()后的路徑上的最后一條邊的權重，其實就是對應的last_edge的權重

relax(v) 松弛圖graph中的頂點v，下面會介紹其操作過程

sp_weight_to(v) 獲取從起點到傳入的頂點v的SP的權重和

has_path_to(v) 檢查圖中從起點出發，是否存在一條路徑能到達頂點v

shortest_path_to(v) 獲取從起點到達頂點v的SP經過的的所有邊

回到DirectedEdge
回到WeightedDigraph
其中用到的的索引最小優先隊列IndexMinPriorityQueue傳送門

運行測試：

if __name__ == '__main__':with open('../DSP.txt', 'r') as f:num_vertices = int(f.readline())num_edges = int(f.readline())graph = WeightedDigraph(num_vertices)edge = DirectedEdgefor _ in range(num_edges):_from, _to, weight = f.readline().split()# print(_from, _to, weight)graph.add_edge(edge(int(_from), int(_to), float(weight)))end = 6DSP = DijkstraSP(graph, 0)# print([e.start() for e in DSP.shortest_path_to(end)] + [end])print(DSP.sp_weight_to(end))print(DSP.has_path_to(end))for e in DSP.shortest_path_to(end):print(f"{e.start()}-->{e.end()}, {e.weight}")

運行結果：

1.5100000000000002 True 0-->2, 0.26 2-->7, 0.34 7-->3, 0.39 3-->6, 0.52

0 → 2 → 7 → 3 → 6

對比參考結果：

DSP.txt

8 15 4 5 0.35 5 4 0.35 4 7 0.37 5 7 0.28 7 5 0.28 5 1 0.32 0 4 0.38 0 2 0.26 7 3 0.39 1 3 0.29 2 7 0.34 6 2 0.40 3 6 0.52 6 0 0.58 6 4 0.93

總結

以上是生活随笔為你收集整理的数据结构之图：加权有向图与dijkstra算法找到最短路径，Python——28的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。