正文

Python实现Dijkstra算法：轻松入门，图解最短路径计算

/0 浏览量
0530

Dijkstra算法是一种经典的图搜索算法，用于找到图中两个顶点之间的最短路径。它适用于图中的所有边都具有非负权重的情形。下面，我们将通过Python代码来实现Dijkstra算法，并使用图解的方式来帮助理解算法的执行过程。

Dijkstra算法简介

Dijkstra算法的基本思想是维护一个集合S，它包含已经找到最短路径的顶点，以及一个包含所有其他顶点的集合U。算法开始时，S为空，U包含图中所有的顶点。然后，算法重复以下步骤：

  1. 从U中选取一个顶点v，它是所有未在S中的顶点中距离源点s最近的顶点。
  2. 将v加入S。
  3. 更新U中所有与v相邻的顶点的距离。

算法结束的条件是S中包含所有顶点。

Python实现Dijkstra算法

下面是Dijkstra算法的Python实现，包括图的表示、算法的执行以及图解的展示。

import heapq

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = {}
    
    def add_edge(self, u, v, w):
        if u in self.graph:
            self.graph[u].append((v, w))
        else:
            self.graph[u] = [(v, w)]
    
    def min_distance(self, dist, spt_set):
        min = float('inf')
        min_index = -1
        
        for v in self.graph:
            if dist[v] < min and v not in spt_set:
                min = dist[v]
                min_index = v
        return min_index
    
    def dijkstra(self, src):
        dist = [float('inf')] * self.V
        dist[src] = 0
        spt_set = set()
        
        for cout in range(self.V):
            u = self.min_distance(dist, spt_set)
            spt_set.add(u)
            
            for v, weight in self.graph[u]:
                if v not in spt_set and dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight
        
        return dist

# 创建图
g = Graph(9)
g.add_edge(0, 1, 4)
g.add_edge(0, 7, 8)
g.add_edge(1, 2, 8)
g.add_edge(1, 7, 11)
g.add_edge(2, 3, 7)
g.add_edge(2, 8, 2)
g.add_edge(2, 5, 4)
g.add_edge(3, 4, 9)
g.add_edge(3, 5, 14)
g.add_edge(4, 5, 10)
g.add_edge(5, 6, 2)
g.add_edge(6, 7, 1)
g.add_edge(6, 8, 6)
g.add_edge(7, 8, 7)

# 运行Dijkstra算法
distances = g.dijkstra(0)

# 打印最短路径
for i in range(len(distances)):
    print(f"Distance from source vertex 0 to vertex {i} is {distances[i]}")

图解Dijkstra算法

为了更好地理解Dijkstra算法的执行过程，我们可以使用以下图解方法：

  1. 初始化：所有顶点的距离都设置为无穷大，除了源点，其距离设置为0。
  2. 选择最短路径：从所有未处理的顶点中选择距离源点最近的顶点。
  3. 更新距离：对于选定的顶点，更新其相邻顶点的距离。
  4. 重复：重复步骤2和3，直到所有顶点的最短路径都被找到。

在实际应用中，我们可以通过在图中绘制节点和边的权重，以及用不同颜色表示已经找到最短路径的顶点，来直观地展示算法的执行过程。

通过以上内容，我们不仅学习了Dijkstra算法的基本原理和Python实现，还通过图解的方式加深了对算法执行过程的理解。希望这篇文章能够帮助你轻松入门Dijkstra算法，并在实际应用中发挥其强大的功能。

-- 展开阅读全文 --