使用python编写程序,通过邻接矩阵实现Dijkstra算法

很高兴回答你的问题！关于使用 Python 编写程序，通过邻接矩阵实现 Dijkstra 算法，我可以给出如下思路：首先，需要初始化一个邻接矩阵，其大小为 N×N，其中 N 表示图中节点的数量。然后，需要给出起点和终点，以及他们之间的距离。接着，通过一定的算法，如迭代，遍历整个图，找出最短路径。最后，输出结果即可。希望我的回答对你有帮助。

相关问题

根据用邻接矩阵实现Dijkstra算法

Dijkstra算法是一种用于求解单源最短路径的经典算法，可以使用邻接矩阵来实现。具体步骤如下：

1. 初始化距离数组dist和标记数组visited，将源点s的距离设为0，其他点的距离设为无穷大，所有点的visited值均为false。

2. 从距离数组dist中选择一个未标记的距离最小的点u，标记该点，并对其所有邻接点v进行松弛操作：如果从源点s到u再到v的距离比从源点s直接到v的距离更短，则更新v的距离dist[v]为新的距离，并将v标记为未访问。

3. 重复步骤2，直到所有节点均被标记为已访问，或者不存在未标记节点的距离小于无穷大的点。

4. 最终距离数组dist中存储了从源点s到所有其他点的最短距离。

下面给出使用邻接矩阵实现Dijkstra算法的代码示例：

import sys

# 用邻接矩阵表示图
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

    # 找到距离最小的未访问节点
    def min_distance(self, dist, visited):
        min_dist = sys.maxsize
        min_index = -1
        for v in range(self.V):
            if dist[v] < min_dist and not visited[v]:
                min_dist = dist[v]
                min_index = v
        return min_index

    # 打印最短路径
    def print_path(self, parent, j):
        if parent[j] == -1:
            print(j, end=' ')
            return
        self.print_path(parent, parent[j])
        print(j, end=' ')

    # Dijkstra算法
    def dijkstra(self, src):
        dist = [sys.maxsize] * self.V
        parent = [-1] * self.V
        dist[src] = 0
        visited = [False] * self.V

        for cout in range(self.V):
            u = self.min_distance(dist, visited)
            visited[u] = True
            for v in range(self.V):
                if self.graph[u][v] > 0 and not visited[v] and \
                        dist[u] + self.graph[u][v] < dist[v]:
                    dist[v] = dist[u] + self.graph[u][v]
                    parent[v] = u

        print("最短路径:")
        for i in range(self.V):
            print(src, "->", i, "距离:", dist[i], "路径:", end=' ')
            self.print_path(parent, i)
            print()

# 测试
g = Graph(9)
g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
           [4, 0, 8, 0, 0, 0, 0, 11, 0],
           [0, 8, 0, 7, 0, 4, 0, 0, 2],
           [0, 0, 7, 0, 9, 14, 0, 0, 0],
           [0, 0, 0, 9, 0, 10, 0, 0, 0],
           [0, 0, 4, 14, 10, 0, 2, 0, 0],
           [0, 0, 0, 0, 0, 2, 0, 1, 6],
           [8, 11, 0, 0, 0, 0, 1, 0, 7],
           [0, 0, 2, 0, 0, 0, 6, 7, 0]]

g.dijkstra(0)

上述代码中，我们使用邻接矩阵来表示图，dist数组存储源点到各个节点的距离，parent数组存储最短路径上每个节点的前驱节点，visited数组表示该节点是否被访问过。在Dijkstra算法中，我们通过找到距离最小的未访问节点，以及对其邻接点进行松弛操作，来逐步求解源点到各个节点的最短距离。最后打印出最短路径和距离即可。

帮我用python写一个用邻接矩阵储存的图的Dijkstra算法

以下是使用邻接矩阵储存的图的Dijkstra算法的Python代码：

# 定义邻接矩阵
graph = [[0, 2, 4, 0, 0, 0],
         [2, 0, 1, 4, 2, 0],
         [4, 1, 0, 1, 3, 0],
         [0, 4, 1, 0, 1, 3],
         [0, 2, 3, 1, 0, 1],
         [0, 0, 0, 3, 1, 0]]

# 定义Dijkstra算法函数
def dijkstra(graph, start):
    # 初始化
    n = len(graph)
    visited = [False] * n
    dist = [float('inf')] * n
    dist[start] = 0
    
    # 运行算法
    for i in range(n):
        # 选择节点
        u = -1
        for j in range(n):
            if not visited[j] and (u == -1 or dist[j] < dist[u]):
                u = j
        
        # 标记节点为已访问
        visited[u] = True
        
        # 更新距离
        for v in range(n):
            if not visited[v] and graph[u][v] != 0:
                new_dist = dist[u] + graph[u][v]
                if new_dist < dist[v]:
                    dist[v] = new_dist
    
    return dist

# 测试算法
print(dijkstra(graph, 0)) # 输出[0, 2, 4, 5, 4, 6]

在这个例子中，我们定义了一个邻接矩阵（graph）来存储图，并且使用Dijkstra算法来计算从节点0开始到其他节点的最短路径。函数dijkstra()接收邻接矩阵graph和起始节点start，返回一个包含从起始节点到每个其他节点的最短距离的列表（dist）。在算法中，我们首先初始化变量visited和dist，然后选择距离起始节点最近的节点，标记为visited并更新dist。重复这个过程直到所有节点都被访问。最后，我们返回dist列表作为结果。在这个例子中，最短路径列表为[0, 2, 4, 5, 4, 6]，表示从节点0到其他节点的最短距离。