The Dijkstra Algorithm for the Shortest Path Problem

Reference: Dijkstra E W. A note on two problems in connexion with graphs[M]//Edsger Wybe Dijkstra: His Life, Work, and Legacy. 2022: 287-290.

m2mDijkstra.py solves the many-to-many shortest path problem (m2mSPP).

The m2mSPP aims to find the shortest path from any source to any destination.

Variables	Meaning
network	Dictionary, {node1: {node2: length, node3: length, ...}, ...}
source	The source node
destination	The destination node
nn	The number of nodes
neighbor	Dictionary, {node1: [the neighbor nodes of node1], ...}
dist	List, the length label associated with each node
path	List, the path label associated with each node
searched_node	List, the nodes that have already been searched
queue	The priority queue that output the label with the minimum length at each iteration

Example

Dijkstra (one-to-one version)

if __name__ == '__main__':
    test_network = {
        0: {1: 62, 2: 44, 3: 67},
        1: {0: 62, 2: 32, 4: 52},
        2: {0: 44, 1: 33, 3: 32, 4: 52},
        3: {0: 67, 2: 32, 4: 54},
        4: {1: 52, 2: 52, 3: 54}
    }
    source = 0
    destination = 4
    print(main(test_network, source, destination))

Output:

{'path': [0, 2, 4], 'length': 96}

Dijkstra (one-to-all version)

if __name__ == '__main__':
    test_network = {
        0: {1: 62, 2: 44, 3: 67},
        1: {0: 62, 2: 32, 4: 52},
        2: {0: 44, 1: 33, 3: 32, 4: 52},
        3: {0: 67, 2: 32, 4: 54},
        4: {1: 52, 2: 52, 3: 54}
    }
    s = 0
    d = 4
    print(main(test_network, s, d))

Output:

{
    'path': [0, 2, 4], 
    'length': 96
}