dijkstra算法python的代码

以下是Dijkstra算法的python代码示例：

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]

    while pq:
        (curr_dist, curr_node) = heapq.heappop(pq)

        if curr_dist > distances[curr_node]:
            continue

        for neighbor, weight in graph[curr_node].items():
            distance = curr_dist + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

希望能够帮到您！

相关问题

dijkstra算法python代码

### 回答1：
当然可以，以下是Dijkstra算法的Python代码：

import heapq

def dijkstra(graph, start):
    # 初始化距离和前驱字典
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0
    previous_vertices = {vertex: None for vertex in graph}

    # 初始化堆
    vertices = [(0, start)]
    heapq.heapify(vertices)

    while vertices:
        # 取出堆中最小距离的节点
        current_distance, current_vertex = heapq.heappop(vertices)

        # 如果当前距离已经大于记录的距离，则直接跳过
        if current_distance > distances[current_vertex]:
            continue

        # 遍历当前节点的所有邻居
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            # 如果新距离比记录距离小，则更新
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous_vertices[neighbor] = current_vertex
                heapq.heappush(vertices, (distance, neighbor))

    return distances, previous_vertices

以上代码实现了Dijkstra算法，接受一个邻接字典表示的图和一个起始节点，返回一个距离字典和前驱字典。其中，邻接字典中每个键值对表示一个节点和它的所有邻居及边权重。

### 回答2：
Dijkstra算法（又称为迪杰斯特拉算法、戴克斯特拉算法）是一种用于计算图中最短路径的贪心算法，广泛应用于路由算法或作为其他图算法的子模块。Dijkstra算法本质上是一种贪心算法，每次找到到某个节点最短路径上的下一个节点，并标记出该节点到起点的距离，推广到整个图上就得到了从起点到各个节点的最短路径。

下面给出Dijkstra算法的Python代码实现：

import heapq

def dijkstra(graph, start):
    distances = {vertex: 0 if vertex == start else float('inf') for vertex in graph}
    heap = [(0, start)]
    while heap:
        current_distance, current_vertex = heapq.heappop(heap)
        if current_distance > distances[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
    return distances

这个算法首先初始化了每个节点到起点的距离，然后将起点加入堆中，堆中存放的是当前最短路径节点和对应的距离。然后每次从堆中取出堆顶元素，如果堆顶元素的距离已经大于当前最短距离，则跳过该节点。如果堆顶元素的距离小于当前最短距离，则更新该节点到起点的距离，并将它的邻居节点加入堆中。

这个实现中使用了一个优先队列来维护最短距离的节点，这使得算法的时间复杂度从O(n^2)降低到了O(m log n)，其中n是节点数，m是边数。

### 回答3：
Dijkstra算法是一种用于寻找带权有向图中单源最短路径的算法。本文将为大家介绍如何用Python语言实现Dijkstra算法。

Dijkstra算法主要思路是通过贪心策略，先找到起点到每个顶点的最短路径，然后利用这些信息进一步缩小搜索范围，最终找到起点到目标点的最短路径。

以下是Dijkstra算法Python代码实现：

#定义初始化函数，将各个点的距离和前一个节点都初始化为-1
def init(graph, start):
    d = {}
    p = {}
    for node in graph:
        d[node] = -1
        p[node] = ""
    d[start] = 0
    return d, p

#定义算法函数。其中graph为图的数据表示（例如邻接矩阵或邻接表），start是起始节点
def dijkstra(graph, start):
    d, p = init(graph, start) 
    unseen_nodes = list(graph.keys()) #未处理的节点集合
    while len(unseen_nodes) > 0:
        #找到当前未处理节点中距离起点最短的节点
        shortest = None
        node = ""
        for temp_node in unseen_nodes:
            if shortest == None:
                shortest = d[temp_node]
                node = temp_node
            elif d[temp_node] < shortest:
                shortest = d[temp_node]
                node = temp_node
        #遍历当前节点的所有出边，更新相邻节点的距离和前一个节点
        for i, weight in graph[node].items():
            if d[i] < 0 or d[i] > d[node] + weight:
                d[i] = d[node] + weight
                p[i] = node
        unseen_nodes.remove(node)
    return d, p

#测试代码
graph = {0: {1: 1, 2: 4},
         1: {2: 2, 3: 5},
         2: {3: 1},
         3: {2: 1, 4: 3},
         4: {0: 3, 3: 1}}
d, p = dijkstra(graph, 0)
print(d) #{0: 0, 1: 1, 2: 3, 3: 4, 4: 3}
print(p) #{0: '', 1: 0, 2: 1, 3: 2, 4: 3}

在上述代码中，我们先定义了一个名为init的初始化函数，它接收一个表示图的数据结构和起点的参数，将所有顶点的距离和前一个节点初始化为-1，将起点的距离设置为0。接下来，我们定义了一个名为dijkstra的算法函数，它接收一个表示图的数据结构和起点的参数，返回一个字典d表示起点到各个顶点的距离，另一个字典p表示与每个节点相邻的前一个节点。该算法首先调用初始化函数，将所有节点的距离和前一个节点初始化，然后遍历所有未处理的节点，在其中找到距离起点最短的节点，将其标记为已处理。然后遍历当前节点的所有出边，更新相邻节点的距离和前一个节点。这个过程重复进行，直到所有节点都被处理完。最后，算法返回d和p两个字典表示起点到各个节点的最短距离和前一个节点。

总结来说，Dijkstra算法是一种非常实用的最短路径算法，在实际应用中具有广泛的应用。Python语言中有许多实现该算法的库，也可以通过简单的代码实现。掌握Dijkstra算法的实现方法，对于提高编程的实战能力和解决实际问题有很大帮助。

带有矩阵的有向图Dijkstra算法python代码

以下是带有矩阵的有向图Dijkstra算法的Python代码实现：

import numpy as np

def dijkstra(graph, start):
    n = graph.shape[0]
    visited = [False] * n
    distances = [float('inf')] * n
    distances[start] = 0
    
    for _ in range(n):
        u = np.argmin([distances[i] for i in range(n) if not visited[i]])
        visited[u] = True
        
        for v in range(n):
            if graph[u][v] != 0 and not visited[v]:
                new_distance = distances[u] + graph[u][v]
                if new_distance < distances[v]:
                    distances[v] = new_distance
                    
    return distances

其中，`graph`是一个Numpy矩阵，表示有向图的邻接矩阵；`start`是起点的编号。该算法返回一个列表，表示起点到每个点的最短距离。