"Graph Algorithms" — Practice

Question 1

Which algorithm finds single-source shortest paths in a graph containing negative edge weights but no negative cycle?

Accepted Answer

B

Question 2

A connected undirected graph has 9 vertices. How many edges does any spanning tree contain?

Accepted Answer

A

Question 3

What is the time complexity of the Floyd-Warshall algorithm on a graph with V vertices and E edges?

Accepted Answer

D

Question 4

A graph has vertices P, Q, R, S, T and edges PQ=2, PR=8, QR=5, QS=3, RS=1, RT=6, ST=4. Find the MST weight using Prim's algorithm starting at P, listing each edge as it is added.

Accepted Answer

Prim grows a single tree, repeatedly adding the cheapest edge leaving the current tree.

Start with the tree containing only P. Its outgoing edges are PQ=2 and PR=8. The cheapest is PQ=2. Add it. Tree: {P, Q}.

Outgoing edges now are PR=8, QR=5, QS=3. The cheapest is QS=3. Add it. Tree: {P, Q, S}.

Outgoing edges now are PR=8, QR=5, RS=1, ST=4. The cheapest is RS=1. Add it. Tree: {P, Q, S, R}.

Outgoing edges now are RT=6 and ST=4, since PR and QR are now internal. The cheapest is ST=4. Add it. Tree: {P, Q, S, R, T}.

All five vertices are included, so the tree is complete with four edges as required.

The MST edges are PQ=2, QS=3, RS=1, ST=4, with total weight 10.

A check against Kruskal confirms it: sorting gives RS=1, PQ=2, QS=3, ST=4, QR=5, RT=6, PR=8. Accept RS, PQ, QS, and ST; then QR would join R's component to Q's, which are already connected through S, so reject it, and likewise RT and PR. The same four edges emerge, as they must since all weights here are distinct and the MST is therefore unique.

Question 5

Run Dijkstra from A on a directed graph with edges A to B = 10, A to C = 3, C to B = 4, C to D = 2, B to D = 1, D to B = 5. Give the final distances and note any revision.

Accepted Answer

Initialise A at 0 and everything else at infinity.

Finalise A at 0. Relax its edges: B becomes 10, C becomes 3.

The closest unfinalised vertex is C at 3. Finalise it. Relax C's edges: B via C is 3 plus 4 = 7, which improves on 10, so B becomes 7. D via C is 3 plus 2 = 5, so D becomes 5.

The closest unfinalised is D at 5. Finalise it. Relax D's edge: B via D is 5 plus 5 = 10, which does not improve on 7, so B stays at 7.

The closest unfinalised is B at 7. Finalise it. Relax B's edge: D via B is 7 plus 1 = 8, which does not improve on D's finalised 5.

Final distances: A = 0, C = 3, D = 5, B = 7.

The revision worth noting is B dropping from 10 to 7 after C was finalised. The direct edge A to B was the first route found but not the shortest, and Dijkstra corrected it because B had not yet been chosen.

The second observation is that relaxing B to D at the end produced no change, because D was already final at 5. That is Dijkstra's guarantee working correctly, and it is exactly the step that a negative edge would invalidate.

Question 6

A directed graph has edges A to C, B to C, C to D, C to E, D to F, E to F. Give a valid topological order using Kahn's algorithm and state how many valid orders exist.

Accepted Answer

Compute in-degrees. A has 0, B has 0, C has 2 from A and B, D has 1 from C, E has 1 from C, F has 2 from D and E.

Kahn's algorithm repeatedly removes a vertex of in-degree zero.

Initially A and B both qualify. Take A. Decrement C to in-degree 1.

Now B qualifies. Take B. Decrement C to 0.

Now C qualifies. Take C. Decrement D and E each to 0.

Now D and E both qualify. Take D. Decrement F to 1.

Now E qualifies. Take E. Decrement F to 0.

Finally take F.

One valid order is A, B, C, D, E, F.

For the count, note two independent choices. A and B can appear in either order at the start, since neither constrains the other, giving 2 possibilities. Likewise D and E can appear in either order in the middle, giving 2 more. C is forced after both A and B, and F after both D and E.

The total number of valid topological orders is 2 times 2 = 4.

A topological order is unique only when the graph contains a Hamiltonian path, forcing a total order. Here neither A-B nor D-E is constrained, so multiple orders exist, and a question expecting one specific answer must specify a tie-break such as lexicographic.

Question 7

Explain how Bellman-Ford detects a negative cycle, why V minus 1 passes suffice in its absence, and what Floyd-Warshall's equivalent test is.

Accepted Answer

First, why V minus 1 passes suffice. A shortest path in a graph without negative cycles never repeats a vertex, since removing a repeated segment could only reduce or preserve the cost. A simple path visits at most V vertices and therefore uses at most V minus 1 edges.

Each pass of Bellman-Ford relaxes every edge once, and it can be shown by induction that after pass i, every shortest path using at most i edges has been found correctly. After V minus 1 passes, every simple path has been accounted for, so all distances are final.

Detection follows immediately. Run one more pass, the V-th. If every distance is already correct, no relaxation can improve anything, so nothing changes. If some distance does improve, then a path using V or more edges is shorter than every simple path, which means it must repeat a vertex, and the repeated segment must have negative total weight.

So any improvement on the V-th pass proves a negative cycle reachable from the source. Note the qualification: reachable from the source. A negative cycle in an unreachable part of the graph is invisible to this test, which is why running Bellman-Ford from a virtual source connected to every vertex is the standard remedy.

Floyd-Warshall's test is simpler. After completion, examine the diagonal. Entry d[i][i] is the shortest path from i back to itself, which should be 0. If any diagonal entry is negative, then a cycle through i has negative total weight.

The advantage of the Floyd-Warshall test is that it detects negative cycles anywhere in the graph, not merely those reachable from one source, because the algorithm considers every pair.

Question 8

Prove that adding a constant to every edge weight leaves the MST unchanged, then show by counterexample that it can change the shortest path.

Accepted Answer

For the MST, let the graph have V vertices and let c be the constant added to every edge weight.

Every spanning tree of a connected graph contains exactly V minus 1 edges. This is a structural fact about trees and is independent of the weights.

So if a spanning tree T had total weight W before the change, its total weight afterwards is W plus (V minus 1) times c, since exactly V minus 1 edges each gained c.

That increment is identical for every spanning tree. Adding the same quantity to every total preserves their relative order, so whichever tree was minimum before remains minimum after. The MST is unchanged.

For shortest paths the argument fails, because different paths contain different numbers of edges and therefore gain different amounts.

Counterexample: a graph with source S, target T, a direct edge S to T of weight 10, and a two-edge route S to M of weight 4 and M to T of weight 4.

Before any change, the two-edge route costs 8 and the direct edge costs 10, so the shortest path goes through M.

Add 3 to every edge. The direct edge becomes 13. The two-edge route becomes 7 plus 7 = 14. The shortest path is now the direct edge.

The transformation penalised the longer path twice and the shorter path once, reversing the ordering.

This is also exactly why Johnson's algorithm cannot simply add a constant to remove negative weights. Its reweighting uses a vertex potential function so that the adjustment along any path telescopes and depends only on the endpoints, which preserves shortest paths where a uniform constant would not.

Question 9

A road network has 10,000 intersections and 30,000 roads with non-negative travel times. Compare the cost of computing all-pairs shortest paths by Floyd-Warshall and by repeated Dijkstra, and recommend one.

Accepted Answer

Establish the parameters. V = 10,000 and E = 30,000, so the average degree is 6 and the graph is very sparse: the maximum possible edge count is about 50 million, and only 30,000 are present.

Floyd-Warshall costs V cubed, which is 10,000 cubed = 10 to the 12 operations. It also needs V squared = 100 million table entries, which at 8 bytes each is 800 MB — already problematic.

Repeated Dijkstra costs V times (V plus E) log V. Computing the inner factor: V plus E is 40,000, and log base 2 of 10,000 is about 13.3, so one run costs roughly 532,000 operations. Multiplying by V gives about 5.3 times 10 to the 9 operations.

Repeated Dijkstra is therefore about 190 times faster than Floyd-Warshall on this input, and the gap widens as the graph gets sparser.

The recommendation is repeated Dijkstra, and the preconditions are satisfied since all travel times are non-negative.

Two caveats are worth stating. The output is the same size either way, at V squared distances, so if the full matrix must be stored the 800 MB cost applies to both; in practice a routing system computes paths on demand from a single source rather than materialising the matrix. And if some edges became negative — modelling a subsidy or a downhill energy gain, say — Dijkstra would be invalid, and the right choice would be Johnson's algorithm, which reweights with one Bellman-Ford run at O(VE) = 3 times 10 to the 8 and then runs Dijkstra everywhere, retaining nearly all the advantage.

Practice — "Graph Algorithms"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities