Skills101
← All practice quizzes

Quiz: Shortest Paths

5 questions · new set on every retakeNo time limitPass: 60%+10 XP on first pass

Find the cheapest route in a weighted graph. Dijkstra with a min-heap traced step by step, Bellman-Ford for negative edges and negative-cycle detection, and the 0-1 BFS trick, in Python and Java.

Log in to take the quiz

Free account · see your score, answers and explanations, earn XP

  1. Question 1

    What does "relaxing" the edge u → v with weight w mean?

  2. Question 2

    What does this print?

    import heapq
    adj = {0: [(1, 5), (2, 1)], 1: [(3, 1)], 2: [(1, 1), (3, 6)], 3: []}
    dist = {0: 0, 1: 99, 2: 99, 3: 99}
    pq = [(0, 0)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    print(dist[1], dist[3])
    
  3. Question 3

    Why can't Dijkstra's algorithm handle negative edge weights?

  4. Question 4

    In the heap version of Dijkstra, why do we skip a popped pair when d > dist[u]?

  5. Question 5

    How many rounds of "relax every edge" does Bellman-Ford need for V nodes (without the check round)?

🎯 Today’s placement challenge — 10 questions, no login. Can you score 10/10?Take today’s challenge →