Dijkstra 算法初探(Dijkstra算法入门详解：从基础到实践)

原创

ithorizon 6个月前 (10-20) 阅读数 18 #后端开发

Dijkstra 算法初探：从基础到实践

一、引言

在计算机科学和图论中，最短路径问题是寻找图中两点之间最短路径的问题。Dijkstra 算法是一种用于解决单源最短路径问题的贪心算法，由荷兰计算机科学家 Edsger W. Dijkstra 于 1959 年提出。本文将从 Dijkstra 算法的基本原理出发，逐步深入到实际应用，帮助读者从基础到实践全面掌握该算法。

二、算法原理

Dijkstra 算法适用于带权图，即图中每条边都有一个权重。算法的基本思想是：从源点出发，逐步将未访问过的顶点添加到已访问集合中，并更新到达每个顶点的最短路径长度。以下是算法的首要步骤：

初始化：设置源点距离为 0，其他顶点距离为无穷大；设置源点为已访问。

选择未访问顶点中距离最小的顶点，将其添加到已访问集合中。

更新未访问顶点的距离：对于每个未访问顶点，计算通过当前已访问顶点到达它的距离，如果这个距离比原来的距离小，则更新它的距离。

重复步骤 2 和 3，直到所有顶点都被访问过。

三、算法实现

以下是 Dijkstra 算法的 Python 实现：


def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    visited = set()
    current_vertex = start
    while current_vertex is not None:
        visited.add(current_vertex)
        for neighbor, weight in graph[current_vertex].items():
            if neighbor not in visited:
                new_distance = distances[current_vertex] + weight
                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance
        next_vertices = {vertex: distances[vertex] for vertex in graph if vertex not in visited}
        if not next_vertices:
            break
        current_vertex = min(next_vertices, key=next_vertices.get)
    return distances