4. [3 points] Recall that a graph of n nodes can be represented as an n x n matr

Question

4. [3 points] Recall that a graph of n nodes can be represented as an n x n matrix (i.e. list of lists) where the value at row i column j gives the "cost" of going directly from node i to node j in the graph. The following O(n3) algorithm computes the lowest cost (shortest) path from each node in the graph to a given destination node d I. Set n equal to the number of nodes in the graph, which is the same as the number II. Set best cost to d from equal to a new list with n elements with no values III. For i in the range 0 to n-1 inclusive, do the following: of rows in the list representing the graph. (None) A. Set best_cost to d fromli] equal to the cost of going directly from node i to node d IV. Repeat the following n-2 times: A. For i in the range 0 to n-1 inclusive, do the following: 1. Forj in the range 0 to n-1 inclusive, do the following Let cost be the cost of going directly from node i to node j in the graph a. b. Let newcost be cost+best cost to d fromli] c. If newcost is less than best cost to d fromfil. then (it's cheaper to go to d from node i via node j, so...) set best cost to d fromlil to newcost V. Return the best_cost to_d list, which will now contain the minimum cost to d from each location.

Explanation / Answer

def shortest_path(graph, start, end, to_print = False):
    """Assumes graph is a Digraph; start and end are nodes
       Returns a shortest path from start to end in graph"""
    return dfs(graph, start, end, [], None, to_print)

def test_sp():
    nodes = []
    for name in range(6): # Create 6 nodes
        nodes.append(Node(str(name)))
    g = Digraph()
    for n in nodes:
        g.add_node(n)
    g.add_edge(Edge(nodes[0], nodes[1]))
    g.add_edge(Edge(nodes[1], nodes[2]))
    g.add_edge(Edge(nodes[2], nodes[3]))
    g.add_edge(Edge(nodes[2], nodes[4]))
    g.add_edge(Edge(nodes[3], nodes[4]))
    g.add_edge(Edge(nodes[3], nodes[5]))
    g.add_edge(Edge(nodes[0], nodes[2]))
    g.add_edge(Edge(nodes[1], nodes[0]))
    g.add_edge(Edge(nodes[3], nodes[1]))
    g.add_edge(Edge(nodes[4], nodes[0]))
    sp = shortest_path(g, nodes[0], nodes[5], to_print = True)
    print('Shortest path is', print_path(sp))
  
    sp = bfs(g, nodes[0], nodes[5])
    print('Shortest path found by BFS:', print_path(sp))

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.