当前位置：首页 > article >正文

力扣刷题之旅：进阶篇（六）—— 图论与最短路径问题

article 2024/9/21 8:41:38

力扣（LeetCode）是一个在线编程平台，主要用于帮助程序员提升算法和数据结构方面的能力。以下是一些力扣上的入门题目，以及它们的解题代码。

--点击进入刷题地址

引言

在算法的广阔天地中，图论是一个非常重要的领域。图论问题常常涉及到节点之间的连接关系和路径问题，而最短路径问题则是其中的经典之一。今天，我们就来一起探索一道关于图论与最短路径的经典题目：“单源最短路径问题”。

题目描述：

给定一个带权有向图，图中包含 n 个节点和 m 条边，每条边都有一个权值表示通过这条边所需的花费。现在，我们需要找出从给定起点到其他所有节点的最短路径。

示例：

输入:

图的邻接表表示如下：
3  
3 2  
1 3 4  
2 1 1  
1 2 2

其中，3 表示节点数量，3 2 表示有 3 条边，第 1 条边的起点是 1，终点是 2，权值是 3；第 2 条边的起点是 1，终点是 3，权值是 4；第 3 条边的起点是 2，终点是 1，权值是 1。

输出:

从节点 1 到其他节点的最短路径长度分别为 [0, 3, 4]。

解题思路：

为了解决这个问题，我们可以使用 Dijkstra 算法。Dijkstra 算法是一种用于解决单源最短路径问题的贪心算法。它的基本思想是从起点开始，逐步向外扩展，不断更新起点到其他节点的最短路径长度。
具体实现时，我们可以使用一个数组 dist 来记录起点到其他节点的最短路径长度，初始时将所有节点的距离都设置为无穷大，除了起点到自身的距离为 0。然后，我们每次从未被访问的节点中选择一个距离最短的节点，更新其相邻节点的距离。重复这个过程，直到所有节点都被访问过为止。

代码实现：

import heapq  
  
def dijkstra(graph, start):  
    n = len(graph)  
    dist = [float('inf')] * n  
    dist[start] = 0  
    heap = [(0, start)]  
      
    while heap:  
        curr_dist, curr_node = heapq.heappop(heap)  
          
        if curr_dist > dist[curr_node]:  
            continue  
          
        for neighbor, weight in graph[curr_node].items():  
            new_dist = curr_dist + weight  
            if new_dist < dist[neighbor]:  
                dist[neighbor] = new_dist  
                heapq.heappush(heap, (new_dist, neighbor))  
      
    return dist