照着视频做了自己作业的Python 实现

我的作业要求

import numpy as np #need this for inf value

#dijkstra function, derivated from lecture note,

#input: adjecent matrix of the graph with corresponding weight of each edge

#input: starting source point

#output: shortest distant from source, previous visited point

def dijkstra(graph, source):

    #initializations

    V = len(graph)

    dist = [np.inf] * V

    prev = [None] * V

    dist[source] = 0

    Q = set(range(V))

    while Q:

        u = min(Q, key=lambda v: dist[v]) #find the smallest distance node. since source point is set to 0, the source will be first one

        Q.remove(u)

        for v in range(V):

            if graph[u][v] != np.inf:

                alt = dist[u] + graph[u][v]

                if alt < dist[v]:

                    dist[v] = alt

                    prev[v] = u

    return dist, prev

#main function, initial graph matrix here. and format a table using return value

if __name__ == '__main__':

    graph = [

        [0, 22, 9, 12, np.inf, np.inf, np.inf, np.inf, np.inf],

        [22, 0, 35, np.inf, np.inf, 36, np.inf, 34, np.inf],

        [9, 35, 0, 4, 65, 42, np.inf, np.inf, np.inf],

        [12, np.inf, 4, 0, 33, np.inf, np.inf, np.inf, 30],

        [np.inf, np.inf, 65, 33, 0, 18, 23, np.inf, np.inf],

        [np.inf, 36, 43, np.inf, 18, 0, 39, 24, np.inf],

        [np.inf, np.inf, np.inf, np.inf, 23, 39, 0, 25, 21],

        [np.inf, 34, np.inf, np.inf, np.inf, 24, 25, 0, 19],

        [np.inf, np.inf, np.inf, 30, np.inf, np.inf, 21, 19, 0]

    ]

    source = 0

    dist, prev = dijkstra(graph, source)

    dist.insert(0,"distance")

    prev.insert(0,"previous")

    data = [["vertices", "0", "1", "2", "3", "4", "5", "6", "7", "8"],

            dist,

            prev]

    print(data[0][0]+"   "+data[1][0]+"   "+data[2][0])

    for i in range(1, 10):

        print("   "+data[0][i]+"         "+str(data[1][i])+"         "+str(data[2][i]))