Dijkstra Python Dijkstra's algorithm in python: algorithms for beginners return the distance between the nodes 6 Stop, if the destination node has been visited. 6. Stop, if the smallest distance among the unvisited nodes is infinity.

2025-06-07

Dijkstra Python Dijkstra 算法（Python 版）：面向初学者的算法

返回节点之间的距离

6 如果目标节点已被访问，则停止。

6. 如果距离最小，则停止

未访问的节点之间是无穷大。

照片由 Ishan @seefromthesky 在 Unsplash 上拍摄

Dijkstra 算法可以帮你找到图中两个节点之间的最短路径。它是每个程序员的必学知识。它的维基百科页面提供了精美的动图和历史。

在本文中，我将使用Rosetta Code中久经考验的实现，并对其进行了一些修改，使其能够处理加权和非加权图数据，同时，我们还可以动态编辑图。我将逐块解释代码。

算法

这个算法非常简单。Dijkstra 只用了 20 分钟就创建了它，现在你也可以在同样的时间内学习编写代码。

  1. 将所有节点标记为未访问并存储它们。
  2. 将初始节点的距离设置为零，将其他节点的距离设置为无穷大。
  3. 选择距离最小的未访问节点，即当前节点。
  4. 查找当前节点未访问的邻居节点，并计算它们经过当前节点的距离。将新计算出的距离与已分配的距离进行比较，并保存较小的值。例如，如果节点 A 的距离为 6，且 AB 边的长度为 2，则经过 A 到 B 的距离为 6 + 2 = 8。如果 B 之前被标记为距离大于 8，则将其更改为 8。
  5. 将当前节点标记为已访问并将其从未访问集合中删除。
  6. 如果目标节点已被访问（在规划两个特定节点之间的路线时），或者未访问节点之间的最小距离为无穷大，则停止。如果不是，则重复步骤 3-6。

Python 实现

首先，导入和数据格式。原始实现建议使用 namedtuple 来存储边数据。我们将完全照做，但会为 cost 参数添加一个默认值。有很多方法可以做到这一点，找到最适合你的方法。

from collections import deque, namedtuple


# we'll use infinity as a default distance to nodes.
inf = float('inf')
Edge = namedtuple('Edge', 'start, end, cost')


def make_edge(start, end, cost=1):
    return Edge(start, end, cost)
Enter fullscreen mode Exit fullscreen mode

让我们初始化数据：

class Graph:
    def __init__(self, edges):
        # let's check that the data is right
        wrong_edges = [i for i in edges if len(i) not in [2, 3]]
        if wrong_edges:
            raise ValueError('Wrong edges data: {}'.format(wrong_edges))

        self.edges = [make_edge(*edge) for edge in edges]
Enter fullscreen mode Exit fullscreen mode

我们来找找顶点。在最初的实现中，顶点是在 __init__ 中定义的，但我们需要在边发生变化时更新它们，所以我们将它们设为一个属性，每次处理该属性时都会重新计算它们。对于大型图来说，这可能不是最好的解决方案，但对于小型图来说，它还是可行的。

    @property
    def vertices(self):
        return set(
            # this piece of magic turns ([1,2], [3,4]) into [1, 2, 3, 4]
            # the set above makes it's elements unique.
            sum(
                ([edge.start, edge.end] for edge in self.edges), []
            )
        )
Enter fullscreen mode Exit fullscreen mode

现在，让我们添加添加和删除功能。

    def get_node_pairs(self, n1, n2, both_ends=True):
        if both_ends:
            node_pairs = [[n1, n2], [n2, n1]]
        else:
            node_pairs = [[n1, n2]]
        return node_pairs

    def remove_edge(self, n1, n2, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        edges = self.edges[:]
        for edge in edges:
            if [edge.start, edge.end] in node_pairs:
                self.edges.remove(edge)

    def add_edge(self, n1, n2, cost=1, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        for edge in self.edges:
            if [edge.start, edge.end] in node_pairs:
                return ValueError('Edge {} {} already exists'.format(n1, n2))

        self.edges.append(Edge(start=n1, end=n2, cost=cost))
        if both_ends:
            self.edges.append(Edge(start=n2, end=n1, cost=cost))
Enter fullscreen mode Exit fullscreen mode

让我们为每个节点寻找邻居：

    @property
    def neighbours(self):
        neighbours = {vertex: set() for vertex in self.vertices}
        for edge in self.edges:
            neighbours[edge.start].add((edge.end, edge.cost))

        return neighbours
Enter fullscreen mode Exit fullscreen mode

现在是算法时间！我重命名了变量，以便更容易理解。

    def dijkstra(self, source, dest):
        assert source in self.vertices, 'Such source node doesn\'t exist'

        # 1. Mark all nodes unvisited and store them.
        # 2. Set the distance to zero for our initial node 
        # and to infinity for other nodes.
        distances = {vertex: inf for vertex in self.vertices}
        previous_vertices = {
            vertex: None for vertex in self.vertices
        }
        distances[source] = 0
        vertices = self.vertices.copy()

        while vertices:
            # 3. Select the unvisited node with the smallest distance, 
            # it's current node now.
            current_vertex = min(
                vertices, key=lambda vertex: distances[vertex])

            # 6. Stop, if the smallest distance 
            # among the unvisited nodes is infinity.
            if distances[current_vertex] == inf:
                break

            # 4. Find unvisited neighbors for the current node 
            # and calculate their distances through the current node.
            for neighbour, cost in self.neighbours[current_vertex]:
                alternative_route = distances[current_vertex] + cost

                # Compare the newly calculated distance to the assigned 
                # and save the smaller one.
                if alternative_route < distances[neighbour]:
                    distances[neighbour] = alternative_route
                    previous_vertices[neighbour] = current_vertex

            # 5. Mark the current node as visited 
            # and remove it from the unvisited set.
            vertices.remove(current_vertex)


        path, current_vertex = deque(), dest
        while previous_vertices[current_vertex] is not None:
            path.appendleft(current_vertex)
            current_vertex = previous_vertices[current_vertex]
        if path:
            path.appendleft(current_vertex)
        return path
Enter fullscreen mode Exit fullscreen mode

我们来使用它吧。

graph = Graph([
    ("a", "b", 7),  ("a", "c", 9),  ("a", "f", 14), ("b", "c", 10),
    ("b", "d", 15), ("c", "d", 11), ("c", "f", 2),  ("d", "e", 6),
    ("e", "f", 9)])

print(graph.dijkstra("a", "e"))
>>> deque(['a', 'c', 'd', 'e'])
Enter fullscreen mode Exit fullscreen mode

上面的整个代码：

from collections import deque, namedtuple


# we'll use infinity as a default distance to nodes.
inf = float('inf')
Edge = namedtuple('Edge', 'start, end, cost')


def make_edge(start, end, cost=1):
  return Edge(start, end, cost)


class Graph:
    def __init__(self, edges):
        # let's check that the data is right
        wrong_edges = [i for i in edges if len(i) not in [2, 3]]
        if wrong_edges:
            raise ValueError('Wrong edges data: {}'.format(wrong_edges))

        self.edges = [make_edge(*edge) for edge in edges]

    @property
    def vertices(self):
        return set(
            sum(
                ([edge.start, edge.end] for edge in self.edges), []
            )
        )

    def get_node_pairs(self, n1, n2, both_ends=True):
        if both_ends:
            node_pairs = [[n1, n2], [n2, n1]]
        else:
            node_pairs = [[n1, n2]]
        return node_pairs

    def remove_edge(self, n1, n2, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        edges = self.edges[:]
        for edge in edges:
            if [edge.start, edge.end] in node_pairs:
                self.edges.remove(edge)

    def add_edge(self, n1, n2, cost=1, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        for edge in self.edges:
            if [edge.start, edge.end] in node_pairs:
                return ValueError('Edge {} {} already exists'.format(n1, n2))

        self.edges.append(Edge(start=n1, end=n2, cost=cost))
        if both_ends:
            self.edges.append(Edge(start=n2, end=n1, cost=cost))

    @property
    def neighbours(self):
        neighbours = {vertex: set() for vertex in self.vertices}
        for edge in self.edges:
            neighbours[edge.start].add((edge.end, edge.cost))

        return neighbours

    def dijkstra(self, source, dest):
        assert source in self.vertices, 'Such source node doesn\'t exist'
        distances = {vertex: inf for vertex in self.vertices}
        previous_vertices = {
            vertex: None for vertex in self.vertices
        }
        distances[source] = 0
        vertices = self.vertices.copy()

        while vertices:
            current_vertex = min(
                vertices, key=lambda vertex: distances[vertex])
            vertices.remove(current_vertex)
            if distances[current_vertex] == inf:
                break
            for neighbour, cost in self.neighbours[current_vertex]:
                alternative_route = distances[current_vertex] + cost
                if alternative_route < distances[neighbour]:
                    distances[neighbour] = alternative_route
                    previous_vertices[neighbour] = current_vertex

        path, current_vertex = deque(), dest
        while previous_vertices[current_vertex] is not None:
            path.appendleft(current_vertex)
            current_vertex = previous_vertices[current_vertex]
        if path:
            path.appendleft(current_vertex)
        return path


graph = Graph([
    ("a", "b", 7),  ("a", "c", 9),  ("a", "f", 14), ("b", "c", 10),
    ("b", "d", 15), ("c", "d", 11), ("c", "f", 2),  ("d", "e", 6),
    ("e", "f", 9)])

print(graph.dijkstra("a", "e"))
Enter fullscreen mode Exit fullscreen mode

PS：对于像我一样读过更多有关巫师的书而不是算法书的人来说，是 Edsger Dijkstra，而不是 Sigismund。

文章来源：https://dev.to/mxl/dijkstras-algorithm-in-python-algorithms-for-beginners-dkc
Devto 翻译
PREV
保护您的数据 API 免受网络爬虫的攻击
NEXT
大O：空间复杂度