#! /usr/bin/env python3 # def dijkstra_test ( ): #*****************************************************************************80 # ## dijkstra_test() tests dijkstra(). # # Discussion: # # We are given a graph G, and a matrix D of pairwise distances, where # Dij is the length of the length joining nodes I and J, or else # is infinity if there is no direct link from node I to node J, # # We seek the minimum distances between node 0 and all other nodes. # # This program sets up a small example problem and solves it. # # The example graph uses 6 nodes, and has the following diagram and # distance matrix: # # N0--15--N2-100--N3 0 40 15 Inf Inf Inf # \ | / 40 0 20 10 25 6 # \ | / 15 20 0 100 Inf Inf # 40 20 10 Inf 10 100 0 Inf Inf # \ | / Inf 25 Inf Inf 0 8 # \ | / Inf 6 Inf Inf 8 0 # N1 # / \ # / \ # 6 25 # / \ # / \ # N5----8-----N4 # # The correct minimum distances are: # # 0 35 15 45 49 41 # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 26 March 2026 # # Author: # # John Burkardt. # # Reference: # # Edsger Dijkstra, # A note on two problems in connexion with graphs, # Numerische Mathematik, # Volume 1, 1959, pages 269-271. # import numpy as np import platform import pprint print ( '' ) print ( 'dijkstra_test():' ) print ( ' numpy version: ' + np.version.version ) print ( ' python version: ' + platform.python_version ( ) ) print ( ' dijkstra() uses Dijkstra\'s algorithm to determine the minimum' ) print ( ' distance from node 0 to each node in a graph,' ) print ( ' given the distances between each pair of nodes.' ) # # Initialize the problem data. # for case in [ 0, 1 ]: if ( case == 0 ): print ( '' ) print ( ' Case 0: Graph is connected:' ) ohd = np.array ( [ \ [ 0, 40, 15, np.inf, np.inf, np.inf ], \ [ 40, 0, 20, 10, 25, 6 ], \ [ 15, 20, 0, 100, np.inf, np.inf ], \ [ np.inf, 10, 100, 0, np.inf, np.inf ], \ [ np.inf, 25, np.inf, np.inf, 0, 8 ], \ [ np.inf, 6, np.inf, np.inf, 8, 0 ] ] ) else: print ( '' ) print ( ' Case 1: Graph is not connected:' ) ohd = np.array ( [ \ [ 0, 40, 15, np.inf, np.inf, np.inf ], \ [ 40, 0, 20, 10, np.inf, np.inf ], \ [ 15, 20, 0, 100, np.inf, np.inf ], \ [ np.inf, 10, 100, 0, np.inf, np.inf ], \ [ np.inf, np.inf, np.inf, np.inf, 0, 8 ], \ [ np.inf, np.inf, np.inf, np.inf, 8, 0 ] ] ) # # Print the distance matrix. # print ( '' ) print ( ' One-link pairwise distance matrix:' ) pprint.pprint ( ohd ) # # Carry out the algorithm. # mind = dijkstra ( ohd ) # # Print the results. # print ( '' ) print ( ' Any path minimal distance to node 0:' ) pprint.pprint ( mind ) # # Terminate. # print ( '' ) print ( 'dijkstra_test():' ) print ( ' Normal end of execution.' ) return def dijkstra ( ohd ): #*****************************************************************************80 # ## dijkstra() uses Dijkstra's minimum distance algorithm. # # Discussion: # # We essentially build a tree by selecting certain edges from the # underlying graph. We start with only node 0 connected # to the tree, and this is indicated by setting CONNECTED(0) = True. # # We initialize MIND(I) to the one step distance from node 0 to node I. # # Now we search among the unconnected nodes for the node MV whose minimum # distance is smallest, and connect it to the tree. For each remaining # unconnected node I, we check to see whether the distance from 0 to MV # to I is less than that recorded in MIND(I), and if so, we can reduce # the distance. # # After NV-1 steps, we have connected all the nodes to 0, and computed # the correct minimum distances. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 26 March 2026 # # Author: # # John Burkardt. # # Input: # # integer ohd[nv,nv]: the distance of the direct link between # nodes I and J. # # Output: # # integer mind[nv]: the minimum distance from the first node to each node. # import numpy as np # # Infer the number of nodes. # nv = ohd.shape[0] # # Start out with only the first node connected to the tree. # connected = np.zeros ( nv, dtype = bool ) connected[0] = True for i in range ( 1, nv ): connected[i] = False # # Initialize the minimum distance to the one-step distance. # mind = np.zeros ( nv ) for i in range ( 1, nv ): mind[i] = ohd[0,i] # # Attach one more node on each iteration. # for step in range ( 1, nv ): # # Find the nearest unconnected node. # md = np.inf mv = -1 for i in range ( 0, nv ): if ( not connected[i] and mind[i] <= md ): md = mind[i] mv = i # # If the search fails, the graph is not connected. # That's OK, it just means some nodes will be correctly assigned as being # infinitely far from the starting node. # if ( mv == - 1 ): break # # Mark this node as connected. # connected[mv] = True # # Having determined the minimum distance to node MV, see if # that reduces the minimum distance to other nodes. # for i in range ( 0, nv ): if ( not connected[i] ): mind[i] = min ( mind[i], mind[mv] + ohd[mv,i] ) return mind def timestamp ( ): #*****************************************************************************80 # ## timestamp() prints the date as a timestamp. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 06 April 2013 # # Author: # # John Burkardt # import time t = time.time ( ) print ( time.ctime ( t ) ) return if ( __name__ == '__main__' ): timestamp ( ) dijkstra_test ( ) timestamp ( )