Single-Source Shortest Path (SSSP) Algorithms Compared: Worked Example and Exam Traps

Choose the right SSSP algorithm by tracing one six-vertex graph with BFS, DAG relaxation, Dijkstra and Bellman-Ford, then test the common traps.

KnowledgeGate Team

Exam prep & CS education

Updated 13 Nov 20266 min read
Single-Source Shortest Path (SSSP) Algorithms Compared: Worked Example and Exam Traps

Knowing the names BFS, Dijkstra and Bellman-Ford is not enough. The real decision is whether the graph is weighted, contains a negative edge, is acyclic, or asks for all pairs rather than one source. A familiar algorithm on the wrong graph can still produce a plausible but incorrect answer. That distinction matters in GATE CS preparation and in implementation. Dijkstra becomes invalid when a negative edge can improve a vertex that has already been finalised.

Single-source shortest paths: define the problem before choosing an algorithm

For a graph G=(V,E) with edge weight w(u,v) and one source S, the SSSP problem finds the minimum total edge weight from S to every reachable vertex. Initialise d[S]=0; an unreachable vertex keeps distance infinity. Minimum total weight does not necessarily mean minimum number of edges.

Do not mix three scopes. A single-pair query asks only for S to T. SSSP asks for S to every vertex. All-pairs shortest paths asks for every ordered source-destination pair. One SSSP run can answer a single-pair query, while Floyd-Warshall solves the larger all-pairs problem.

The earlier Shortest Path Algorithms: Dijkstra, Bellman-Ford and Floyd-Warshall guide traces each major method on a separate example. Here, one fixed graph isolates how unit weights, acyclicity, negative edges and source scope change the SSSP choice. Relaxation supplies the common operation: if d[u] + w(u,v) < d[v], update d[v] and parent[v].

SSSP algorithms compared: BFS, DAG relaxation, Dijkstra and Bellman-Ford

Method

Correct input condition

Negative edges

Reachable negative cycle

Core idea

Standard time

BFS

Unweighted graph or every edge has the same unit cost

Not a weighted-SSSP method

Not applicable to its intended model

Queue by hop level

O(V+E)

DAG shortest path

Weighted directed acyclic graph

Allowed

Impossible in a DAG

Relax once in topological order

O(V+E)

Dijkstra

All reachable edge weights are non-negative

Not allowed

Outside its precondition

Finalise the smallest tentative distance greedily

O((V+E) log V) with adjacency list and binary heap

Bellman-Ford

General directed weighted graph

Allowed

Detects one reachable from the source

Repeated edge relaxation

O(VE)

Choose in that order. Unit weights imply BFS. A known DAG permits one topological pass even with negative edges. Otherwise, Dijkstra needs all relevant edges to be non-negative; Bellman-Ford handles possible negative edges or reachable negative-cycle detection.

Fully worked example: run one six-vertex graph four ways

Use vertices {S,A,B,C,D,T}, source S, and directed edges S->A(2), S->B(5), A->C(2), A->D(7), B->C(-6), B->D(4), C->D(2), C->T(5), D->T(1). The edge B->C=-6 is the only negative edge, and the graph has no cycle.

Correct weighted DAG highlights S-B-C-D-T with cost 2 and shows B to D weight 4, with no B to T edge.

For DAG relaxation, take topological order S,A,B,C,D,T. Processing S gives A=2, B=5. Processing A gives C=4, D=9. Processing B improves C from 4 to 5+(-6)=-1, while D stays 9. Processing C gives D=min(9,-1+2)=1 and T=-1+5=4. Processing D improves T to 1+1=2.

The final distances are d(S)=0, d(A)=2, d(B)=5, d(C)=-1, d(D)=1, d(T)=2. The shortest S to T path is S->B->C->D->T, with weight 5-6+2+1=2.

For Bellman-Ford, scan edges in this deliberately awkward order: C->D, D->T, C->T, A->C, A->D, S->A, B->C, B->D, S->B.

Stage

S

A

B

C

D

T

Initial

0

infinity

infinity

infinity

infinity

infinity

After pass 1

0

2

5

infinity

infinity

infinity

After pass 2

0

2

5

-1

9

infinity

After pass 3

0

2

5

-1

1

2

After pass 4

0

2

5

-1

1

2

Pass 4 makes no update, so early stopping is safe. To reconstruct the path, follow parents as T<-D<-C<-B<-S; distance labels alone do not identify the route.

The same graph separates hop count from Dijkstra's weight precondition

Ignore the numerical weights for a moment. With outgoing neighbours processed alphabetically, BFS produces hop levels S:0, A:1, B:1, C:2, D:2, T:3. It correctly minimises hops in an unweighted interpretation. Its three-edge route is not evidence of minimum weighted cost, because the true weight-2 route uses four edges.

Now misapply Dijkstra. The extraction order is S(0), A(2), C(4), B(5), D(6), T(7). When B is extracted, B->C=-6 would improve C from 4 to 5-6=-1, but C has already been finalised. The wrong labels are C=4, D=6, T=7. This does not refute Dijkstra. It violates Dijkstra's non-negative-edge precondition.

Change only B->C from -6 to +6. Dijkstra is now valid, and all weighted methods return C=4, D=6, T=7.

Four-column chart comparing BFS, DAG relaxation, Dijkstra and Bellman-Ford on one graph, showing why Dijkstra fails on the negative edge.

Why the guarantees differ, plus the all-pairs boundary

BFS processes paths by increasing edge count. DAG relaxation works because predecessors precede successors. In Dijkstra's algorithm, once every edge weight is non-negative, the smallest tentative label cannot be improved by a later edge, so extracting it as final is provably safe. After pass i, Bellman-Ford has found every shortest path using at most i edges. That is why V-1 passes suffice when no reachable negative cycle exists, since a simple shortest path uses at most V-1 edges.

Floyd-Warshall handles negative edges and computes all pairs in O(V^3) time and O(V^2) space. A route through a negative cycle has no finite minimum. Do not choose it for a one-source request.

High-value SSSP mix traps: edge shifts, negative cycles and parents

Adding the same constant to every edge can change the shortest path. Direct edge S->T=5 loses to S->X=2 and X->T=2, total 4. Add 2 per edge: the direct route becomes 7, while the two-edge route becomes 4+4=8, so the winner switches. Multiplying every edge by the same positive constant preserves path ordering; adding per edge favours fewer-edge paths.

Return to the main graph and add only D->B(3). The reachable cycle B->C->D->B has weight -6+2+3=-1. Use the earlier scan order, followed by D->B. After the five required passes, labels include B=3, C=-2, D=0, T=1. On the extra scan, B->C lowers C from -2 to -3, proving a reachable negative cycle. Vertices on or reachable from that cycle have no finite shortest distance.

Two habits close out the remaining traps. Never relax an edge whose tail vertex is still at distance infinity, and update parent[v] only when a strict distance improvement occurs. Keep the two records straight: the distance array gives the costs, while the parent chain gives the actual route.

How exam-style questions test SSSP comparisons

Exam questions ask you to choose from the input conditions, trace a stated pass or extraction order, test an edge transformation, or identify a reachable negative cycle.

Try these against the worked graph:

After B is processed in the DAG pass, what is d(C)? The answer is d(C)=-1, since 5 + (-6) = -1.

After Bellman-Ford pass 2 in the given edge order, what is d(D)? The answer is d(D)=9.

Why can Dijkstra not finalise C first here? Because the negative edge B->C has not yet been examined, so C's label can still fall.

Use the GATE Test Series for timed Algorithms practice.

The short version and the next step

Use this decision checklist:

  1. Identify unit or weighted edges.

  2. Check whether the graph is a DAG.

  3. Scan for negative weights.

  4. Decide one source versus all pairs.

  5. Decide whether negative-cycle detection is required.

BFS is for unit weights, DAG relaxation for an acyclic weighted graph, Dijkstra for non-negative weights, and Bellman-Ford for negative edges or cycle detection.

Redraw the graph and reproduce both tables without looking. Then change B->C to +6 and predict every final label. Continue with structured GATE Algorithms preparation.