Paths and all-pairs in Python

Questions 1 to 5 of 8

1. 1. Predict the output of this program. ``python import math INF = math.inf d = [[INF] * 3 for _ in range(3)] for i in range(3): d[i][i] = 0 d[0][1] = 2 d[1][2] = 2 d[2][0] = 1 d[0][2] = 7 for k in range(3): for i in range(3): for j in range(3): d[i][j] = min(d[i][j], d[i][k] + d[k][j]) print(d[0][2], d[1][0]) `` What does it print?

   7 34 34 INF2 1
2. 2. The code below runs BFS from vertex 0 and prints the parent list. What does it print? ``python from collections import deque n = 5 edges = [(0, 2), (0, 1), (1, 3), (2, 3), (3, 4)] adj = [[] for _ in range(n)] for a, b in edges: adj[a].append(b) adj[b].append(a) parent = [-1] * n seen = [False] * n queue = deque([0]) seen[0] = True while queue: u = queue.popleft() for v in adj[u]: if not seen[v]: seen[v] = True parent[v] = u queue.append(v) print(parent) ``

   [-1, 0, 0, 1, 3][-1, 0, 0, 2, 4][-1, 0, 0, 2, 3][0, 0, 0, 2, 3]
3. 3. The route from 0 to 3 comes back as [3, 2, 0] instead of [0, 2, 3]. Which part of this code causes it? ``python def path_to(parent, target): path = [] v = target while v != -1: path.append(v) v = parent[v] return path ``

   The loop should start at the source instead of the targetpath = [] should be path = (), because a tuple keeps its items in order and a list does notThe loop condition v != -1 stops one step too earlypath.append(v) adds each vertex to the end, so the walk from the target builds the route backwards
4. 4. This version of path_to is meant to return an empty list only for a target that cannot be reached. What is wrong with it? ``python def path_to(parent, target): if parent[target] == -1: return [] path = [] v = target while v != -1: path.insert(0, v) v = parent[v] return path ``

   Nothing is wrong, because the parent list alone always tells an unreachable vertex from the sourceIt loops forever when the target is 0, because the loop never reaches -1It returns [] for the source itself, because the source also has parent -1It returns [target] for an unreachable target, because the loop adds the target before it stops
5. 5. Floyd-Warshall runs its innermost line once for every combination of k, i and j. How many times does the innermost line run for a graph with 100 vertices?

   Type a number.