迪杰斯特拉算法输出完整代码

以下是迪杰斯特拉算法的完整代码实现，包括使用邻接矩阵和邻接表两种方式实现：

使用邻接矩阵实现：

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 print_solution(self, dist):
        print("Vertex \t Distance from Source")
        for node in range(self.V):
            print(node, "\t\t", dist[node])

    def min_distance(self, dist, sptSet):
        min_dist = sys.maxsize
        for v in range(self.V):
            if dist[v] < min_dist and not sptSet[v]:
                min_dist = dist[v]
                min_index = v
        return min_index

    def dijkstra(self, src):
        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

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

        self.print_solution(dist)

# 测试代码
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)

使用邻接表实现：

import sys
from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)

    def add_edge(self, u, v, w):
        self.graph[u].append((v, w))

    def print_solution(self, dist):
        print("Vertex \t Distance from Source")
        for node in range(self.V):
            print(node, "\t\t", dist[node])

    def min_distance(self, dist, sptSet):
        min_dist = sys.maxsize
        for v in range(self.V):
            if dist[v] < min_dist and not sptSet[v]:
                min_dist = dist[v]
                min_index = v
        return min_index

    def dijkstra(self, src):
        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):
            u = self.min_distance(dist, sptSet)
            sptSet[u] = True
            for v, w in self.graph[u]:
                if not sptSet[v] and dist[v] > dist[u] + w:
                    dist[v] = dist[u] + w

        self.print_solution(dist)

# 测试代码
g = Graph(9)
g.add_edge(0, 1, 4)
g.add_edge(0, 7, 8)
g.add_edge(1, 0, 4)
g.add_edge(1, 2, 8)
g.add_edge(1, 7, 11)
g.add_edge(2, 1, 8)
g.add_edge(2, 3, 7)
g.add_edge(2, 5, 4)
g.add_edge(2, 8, 2)
g.add_edge(3, 2, 7)
g.add_edge(3, 4, 9)
g.add_edge(3, 5, 14)
g.add_edge(4, 3, 9)
g.add_edge(4, 5, 10)
g.add_edge(5, 2, 4)
g.add_edge(5, 3, 14)
g.add_edge(5, 4, 10)
g.add_edge(5, 6, 2)
g.add_edge(6, 5, 2)
g.add_edge(6, 7, 1)
g.add_edge(6, 8, 6)
g.add_edge(7, 0, 8)
g.add_edge(7, 1, 11)
g.add_edge(7, 6, 1)
g.add_edge(7, 8, 7)
g.add_edge(8, 2, 2)
g.add_edge(8, 6, 6)
g.add_edge(8, 7, 7)
g.dijkstra(0)