• 注册
当前位置:代码四四五 > python >正文

Dijkstra算法的Python实现及其相关知识解析

本文介绍了Dijkstra算法的相关知识,包括最短路径的定义、Dijkstra算法的原理及实现、时间复杂度分析等,并提供了Python实现示例代码。Dijkstra算法是一种常用的最短路径算法,能够在有向带权图中找到一个顶点到其他所有顶点的最短路径。通过本文的介绍和示例代码,读者可以深入了解这一算法的实现方式和应用场景。

import heapq

def dijkstra(graph, start):
    """
    :param graph: 图的邻接矩阵,graph[i][j]表示从顶点i到顶点j的距离,若i和j不相邻则数字为0
    :param start: 起始顶点
    :return: 返回起始顶点到各个顶点的最短路径及距离
    """
    n = len(graph)
    dist = [float("inf") for _ in range(n)]  # 存储起始顶点到各个顶点的距离,默认为无穷大
    dist[start] = 0  # 起始节点到起始节点的距离为0
    visited = set()  # 记录已访问的节点
    heap = [(0, start)]  # heap中存储(起始节点到该节点的距离,该节点)的元组

    while heap:
        (d, v) = heapq.heappop(heap)  # 取出距起始节点最近的下一个节点
        if v in visited:  # 如果该节点已经访问过,则跳过
            continue
        visited.add(v)
        for w in range(n):  # 对于距离v相邻的节点w
            cost = dist[v] + graph[v][w]  # 更新起始节点到w的距离
            if cost < dist[w]:
                dist[w] = cost
                heapq.heappush(heap, (cost, w))  # 将(新的距离,该节点)元组放入heap中

    return dist

# 测试
if __name__ == "__main__":
    graph = [
        [0, 1, 3, 0],
        [1, 0, 2, 4],
        [3, 2, 0, 5],
        [0, 4, 5, 0]
    ]
    start = 0
    print("起始节点到各个节点的最短路径分别为:")
    print(dijkstra(graph, start))

# 输出结果:起始节点到各个节点的最短路径分别为:[0, 1, 3, 7]

免责申明:文章和图片全部来源于公开网络,如有侵权,请通知删除 162202241@qq.com

最新评论
  • 袁莉明
    2024-03-29 电脑端
    # 1楼
    dijkstra算法path

    个人签名,ta还没设置签名

    拉黑 举报 打赏 回复
  • 秦琬枝
    2024-03-29 电脑端
    # 2楼
    dijkstra算法csdn

    个人签名,ta还没设置签名

    拉黑 举报 打赏 回复
  • 瞿韵良
    2024-03-29 电脑端
    # 3楼
    dijkstra算法简单理解

    个人签名,ta还没设置签名

    拉黑 举报 打赏 回复
  • 吕慧
    2024-03-29 电脑端
    # 4楼
    dijkstra算法分析

    个人签名,ta还没设置签名

    拉黑 举报 打赏 回复
  • 夔琴
    2024-03-29 电脑端
    # 5楼
    dijkstra算法基本原理

    个人签名,ta还没设置签名

    拉黑 举报 打赏 回复
  • 殷毅瑾
    2024-03-29 电脑端
    # 6楼
    dijkstra算法视频讲解

    个人签名,ta还没设置签名

    拉黑 举报 打赏 回复
  • 韦真
    2024-03-29 电脑端
    # 7楼
    dijkstra算法代码c

    个人签名,ta还没设置签名

    拉黑 举报 打赏 回复
  • 茹雅
    2024-03-29 电脑端
    # 8楼
    dijkstra算法程序

    个人签名,ta还没设置签名

    拉黑 举报 打赏 回复
  • 胥广
    2024-03-29 电脑端
    # 9楼
    dijkstra算法中path

    个人签名,ta还没设置签名

    拉黑 举报 打赏 回复

欢迎您发表评论:

请登录之后再进行评论

登录