# Warshall's algorithm to find the shortest paths between n points. # This program uses the following additional programming techniques. # Some but not all of these techniques exist in other programming languages. # When defining a function, you can use optional parameters: def f(a,b=0,c=True): # 0 is default value for b and True is default value for c if c: return a else: return b #f # This function can be called with 1, 2, or 3 arguments. The default value # of b is 0 and the default value of c is True. so calling f(1) is the # same as calling f(1,0,True) and calling f(1,2) is the same as calling # f(1,2,True). # Passing arguments by name: what if you want to use the default value for # b but a different value for c? You can in fact pass arguments by name: # calling f(1,c=False) is the same as calling f(1,0,False). In fact, if # you pass arguments by name you can switch the ordering of the arguments: # f(c=False,a=2,b=3) is the same as f(2,3,False) and f(c=False,a=2) is the # same as f(s,0,False). # Features such as these are convenient but not essential to understanding # programming. You are required to understand them but you don't have to # use them in your own programs (same with for loops). ############### A weighted graph consists of several nodes or # "vertices" and "edges" connecting them. Each edge also has a weight # or "cost", which is a non-negative integer associated with the edge. # An edge can be one directional or bidirectional. If all edges are # bidirectional then the graph is "undirected", otherwise it is # "directed". A path in the graph from vertex i to vertex k is a series of # edges connecting i to k (starting at i and ending in k). The cost of # the path is the sum of the costs of all edges in the path. A minimum # cost path is a path with the lowest possible cost (but there could be # more than one path with the same cost). Warshall's Algorithm is a # relative simple (but not the best) way to find the minimal cost path from # one vertex to another. One advantage of this algorithm is that it doesn't # just find the best path from one node to another, but the best paths from # every node to every other node in the graph. This algorithm represents # the graph using a 2D array (aka a "matrix"). If there are N vertices then # we need a NxN array: the array is always "square". Each vertex is # associated with an array index. If the array is M, then initially # M[i][i] = 0, which means that there is cost-0 edge from each vertex to # itself. M[i][k] = c if there is an edge from vertex i to vertex k with # cost of c, otherwise, M[i][k] = infinity, which indicates that there is # no direct edge from i to k (but that doesn't mean there's no PATH, which # the algorithm will find). from math import inf # infinity, only added since Python 3.5 # if using earlier version of python, use 2**64 as hack. # or use -1, and recognize it as infinity. # the following function creates and returns a 2D array of size rowsxcols # and where the values are all initialized to initval def create2d(rows,cols,initval): A =[] for i in range(0,rows): A.append([initval]*cols) return A #create2d # print2d takes optional names parameter to map indices to names def print2d(A,names=[]): rows,cols= len(A),len(A[0]) if len(names)==0: names = range(0,max(rows,cols)) # print column indices as first row: print("\t",end="") # leave some room for k in range(0,cols): print(names[k],end=":\t") print("") # newline for i in range(0,rows): print(names[i],end=":\t") # first print row index for k in range(0,cols): print(A[i][k],end="\t") # ends in tab, not in newline print("") # newline after inner loop # for i, k #print2d # executes warshall's algorithm on nxn 2d array A, returns path matrix def warshall(A): N = len(A) # assume A is a nxn array, N is rows and cols # creat next-hop matrix: if NH[i][k]=m, then m is the "next hop" from i to k # if there's no known path from i to k, then we can set NH[i][k]=-1 NH = create2d(N,N,-1) # next-hop matrix i = 0 while i