说明
1、Dijkstra算法是经典的最短路径算法,它是数据结构、图论、运筹学等基础教学算法。
令人感兴趣的是,Dijkstra算法通常是按照贪心方法来描述的,而在运筹学中把Dijkstra算法视为动态规划。
2、Dijkstra算法从起始点开始,采用贪心法。
每一遍遍历一个距离起点最近且没有到达的邻接顶点,层层展开,直至结束。
Dijkstra算法求解加权最短路径的最优解,其时间复杂度为O^2。当边数远小于n^2时,复杂度可以降低,并以堆结构的形式将其降低为O`(m+n)log(n))。
Dijkstar算法无法处理负权边,这是由贪心法的选择规则所决定的。
实例
def dijstra(adj, src, dst, n): dist = [Inf] * n dist[src] = 0 book = [0] * n # 记录已经确定的顶点 # 每次找到起点到该点的最短途径 u = src for _ in range(n-1): # 找n-1次 book[u] = 1 # 已经确定 # 更新距离并记录最小距离的结点 next_u, minVal = None, float('inf') for v in range(n): # w w = adj[u][v] if w == Inf: # 结点u和v之间没有边 continue if not book[v] and dist[u] + w < dist[v]: # 判断结点是否已经确定了, dist[v] = dist[u] + w if dist[v] < minVal: next_u, minVal = v, dist[v] # 开始下一轮遍历 u = next_u print(dist) return dist[dst]
本文教程操作环境:windows7系统、Python 3.9.1,DELL G3电脑。
苹果芯片加持下PyTorch如何利用GPU和NPU?
NumPy保存和加载数据时如何处理None值?
遇到Python读取Excel测试用例时出现“list index out of range”错误,可以按照以下步骤解决:检查Excel文件内容:确保Excel文件中的数据完整且格式正确。错误常见于尝试访问不存在的列表索引,因此确认每一行都有足够的数据。查看代码逻辑:检查读取Excel文件的代码,特别是涉及到列表索引的部分。确保你访问的索引在列表的有效范围内。例如,如果列表长度为5,索引只能从0到4。调试代码:在可能出错的地方添加打印语句或使用调试器,查看变量的值和列表的长度,确保你在正确的位置访问正确的
微信扫码后小窗口变空白?解决方法在这里!
TCP端口占用:服务端程序退出后,端口为何依然被占用且如何解决?
初学者 Python 项目:使用 OpenCV 和 Mediapipe 构建增强现实绘图应用程序