Dijkstra算法

给定一个源顶点 (s) 从一组顶点 (V) 在加权有向图中，其中所有边权重 (w(u, v)) 均是非负的，找到最短路径权重 (d(s, v)) 从源头 (s) 对于所有顶点 (v) 出现在(Graph)中。

(Dijkstra) 算法是一种求解非负权图上单源最短路径的算法。

算法分析

我们以下图为例，计算起点 (A) 到每个顶点的最短距离：

我们先定义一个 (distances[5]) 数组，用于记录起点到所有顶点的距离，这里我们假设数组中的元素序号 0 ~ 4 分别表示顶点 A ~ E ，将数组中的所有元素都初始化为无效值（或者无穷大），即：

初始条件

由于，我们从顶点 (A) 开始，所以顶点 (A) 的距离为 (0)，即 (distances[0] = 0) 。

第一次查找

我们用(S)记录最短路径，从顶点A开始计算A的邻居节点B，E，由于B可以通过A直接到达，我们暂时记录 (S_{AB} = 10)，，同理，顶点A到顶点E的距离 (S_{AE} = 3)，即

第二次查找

我们考虑，从 ({S_{AB}, S_{AE}}) 中选择权重最小的边 $S_{AE}作为路径，继续查找：

第三次查找

第四次查找

第五次查找

第六次查找

代码模板

这里我们直接给出代码模板：

import heapq
from typing import List, Tuple

class NodeState(object):
    def __init__(self, node_id: int, distance: int = 0):
        # 节点id
        self._id = node_id
        # 从起点到当前节点的距离
        self._distance = distance

    def get_id(self):
        return self._id

    def get_distance(self):
        return self._distance

    def __lt__(self, other):
        """ 小的节点在堆顶 """
        return self.get_distance() - other.get_distance()


def dijkstra(start: int, graph: List[List[Tuple[int]]]):
    """ 单源最短路径：计算从起点到每个节点的距离
    :param start: 起点
    :param graph: 邻接表
    :return:
    """
    distances = [float("INF")] * len(graph)
    distances[start] = 0
    # 使用优先级队列保存所有的节点，保证堆顶的元素最小
    queue = list()
    heapq.heappush(queue, NodeState(start, 0))
    while len(queue) != 0:
        current_stat = heapq.heappop(queue)
        if current_stat.get_distance() > distances[current_stat.get_id()]:
            continue

        for neighbor in graph[current_stat.get_id()]:
            # 当前节点的序号
            _id = neighbor[0]
            # 起点到当前节点的距离
            distance = distances[current_stat.get_id()] + neighbor[1]
            if distance < distances[_id]:
                distances[_id] = distance
                heapq.heappush(queue, NodeState(_id, distance))

    return distances

应用

应用1：Leetcode.743

题目

743. 网络延迟时间

题目分析

这是一道典型的求最短路径的算法：加权有向图，没有负权重边，求最短路径。

我们将传播时间看成边(V)的权重，我们用邻接表来表示有向加权图，最后直接利用(Dijkstra)算法，计算出从起点到终点的每一个节点的最短传播路径即可。

这里我们直接给出 (Dijkstra) 算法的模板，套用模板即可。

需要注意：题目中的节点序号是从 (1) 开始的，所以我们生成邻接矩阵的时候，将所有的节点序号都减一，保证节点序号从 (0) 开始。

代码实现

import heapq
from typing import List, Tuple

class NodeState(object):
    def __init__(self, node_id: int, distance: int = 0):
        # 节点id
        self._id = node_id
        # 从起点到当前节点的距离
        self._distance = distance

    def get_id(self):
        return self._id

    def get_distance(self):
        return self._distance

    def __lt__(self, other):
        """ 小的节点在堆顶 """
        return self.get_distance() - other.get_distance()

def dijkstra(start: int, graph: List[List[Tuple[int]]]):
    """ 单源最短路径：计算从起点到每个节点的距离
    :param start: 起点
    :param graph: 邻接表
    :return:
    """
    distances = [float("INF")] * len(graph)
    distances[start] = 0
    # 使用优先级队列保存所有的节点，保证堆顶的元素最小
    queue = list()
    heapq.heappush(queue, NodeState(start, 0))
    while len(queue) != 0:
        current_stat = heapq.heappop(queue)
        if current_stat.get_distance() > distances[current_stat.get_id()]:
            continue
        for neighbor in graph[current_stat.get_id()]:
            # 当前节点的序号
            _id = neighbor[0]
            # 起点到当前节点的距离
            distance = distances[current_stat.get_id()] + neighbor[1]
            if distance < distances[_id]:
                distances[_id] = distance
                heapq.heappush(queue, NodeState(_id, distance))
    return distances

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = [list() for _ in range(n)]
        for _time in times:
            graph[_time[0] - 1].append((_time[1] - 1, _time[2]))

        distances = dijkstra(start=k - 1, graph=graph)

        _time = max(distances)
        if _time == float("INF"):
            _time = -1
        return _time