代码如下:""" File: fromexample.py Project 12.9 Defines and tests the all pairs shortest paths algorithm of Floyd. Uses the graph from Figure 12.19 of the text, as represented in the file example.txt. """ from graph import LinkedDirectedGraph import random from arrays import Array # Functions for working with infinity def isLessWithInfinity(a, b): """Returns False if a == b or a == INFINITY and b != INFINITY. Otherwise, returns True if b == INFINITY or returns a < b.""" if a == LinkedDirectedGraph.INFINITY and b == LinkedDirectedGraph.INFINITY: return False elif b == LinkedDirectedGraph.INFINITY: return True elif a == LinkedDirectedGraph.INFINITY: return False else: return a < b def addWithInfinity(a, b): """If a == INFINITY or b == INFINITY, returns INFINITY. Otherwise, returns a + b.""" if a == LinkedDirectedGraph.INFINITY or b == LinkedDirectedGraph.INFINITY: return LinkedDirectedGraph.INFINITY else: return a + b def minDistance(a, b): if isLessWithInfinity(a, b): return a else: return b # Define a function that uses Floyd's algorithm def allPairsShortestPaths(matrix): """ please complete the Floyd algorithm here """ pass # Define a function to print a labeled distance matrix def printDistanceMatrix(matrix, table): """Prints the distance matrix with rows and columns labels with the index positions and vertex labels.""" labels = Array(len(table)) index = 0 labelWidth = 0 indexWidth = 0 for label in table: labels[table[label]] = label labelWidth = max(labelWidth, len(str(label))) indexWidth = max(indexWidth, len(str(index))) index += 1 weightWidth = 0 for row in range(matrix.getHeight()): for column in range(matrix.getWidth()): weightWidth = max(weightWidth, len(str(matrix[row][column]))) weightWidth = max(weightWidth, labelWidth, indexWidth) topRowLeftMargin

这段代码定义并测试 Floyd 的全部最短路径算法，使用的是文本图 12.19 中的图，该图以 example.txt 文件的形式表示。有从graph中导入LinkedDirectedGraph，从arrays中导入Array，还有随机数生成函数。