• 欢迎光临~

# 最短路径：Dijkstra算法

• Dijkstra算法
• 算法分析
• 代码模板
• 应用
• 应用1：Leetcode.743
• 题目
• 题目分析
• 代码实现

# Dijkstra算法

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

## 算法分析

[distances[i] = MAX ]

[distance[1] = 10, quad distance[4] = 3 ]

## 代码模板

``````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. 网络延迟时间

#### 代码实现

``````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
``````