是不是很简单,就是广度搜索,加上贪心的思想,先找出起点 s 开始直接相连的点(广度搜索),然后找出与 s 第一个最近的点(贪心),从最近的点出发,再次广度,再次贪心,就可以找出距离起点 s 第二个最近的点...算法时间复杂度 O(E+Vlog(v)) ,E 是边的数量,V 是定点的数量,Vlog(v) 其实就是堆排序的时间复杂度。
算法时间复杂度 O(E+V) 邻接矩阵的空间复杂度。...假如有 6 个顶点,使用邻接矩阵来表示:
adjacency_matrix = [
[0, 7, 9, -1, -1, 14],
[7, 0, 10, 15, -1, -1],...dijkstra 算法,里面有注释,不难看懂:
import sys
import heapq
max = sys.maxsize
vertices_number = 6
adjacency_matrix...# 取出 from_vertex1 的邻居节点,
for index, distance in enumerate(adjacency_matrix[from_vertex1]):