Single-Source Shortest Path SSSP: Applying Dijkstra to the Given Graph | AI Research

Single-Source Shortest Path (SSSP): Applying Dijkstra to the Given Graph

Verified Sources

Sep 12, 2026

Dijkstra’s Algorithm (SSSP) - Relaxation + Priority Queue

Single-source shortest path SSSP focuses on computing minimum path costs from a given source $s$ to every vertex in a weighted graph. The standard approach when all edge weights are nonnegative is Dijkstra’s algorithm, which repeatedly applies relaxation to edges from the currently best-known frontier until no further improvements are possible.

Key idea (relaxation)

For an edge $(u,v)$ with weight $w(u,v)$ , relaxation updates:

\text{dist}[v] \leftarrow \min(\text{dist}[v],\ \text{dist}[u] + w(u,v)).

When to use which algorithm

If all weights are nonnegative: use Dijkstra’s algorithm.
If there may be negative weights: use Bellman–Ford.

⚠️ Note on your prompt: the graph is provided as an image link. In this chat environment I can’t open or read the image content, so I cannot reliably extract the exact vertices, edges, weights, or the required source node. To still help you “apply SSSP,” I provide a complete, fill-in-by-graph workflow (tables, relaxation order, and how to compute final distances/paths) that you can apply directly once you list the edges and weights.

Pro Tip: Turn the image into an edge list first

Write the graph as an edge list like (u, v, w) for each directed edge (or ensure undirected edges appear in both directions). Then run the same Dijkstra workflow below and you’ll get the exact shortest distances and parent pointers.

Dijkstra only works for nonnegative weights

If any edge weight is negative, you must switch to Bellman–Ford; otherwise Dijkstra’s greedy choice can fail.

How to Apply SSSP (Dijkstra) to Your Graph

Extract edges + weights

1) Parse graph

From the image, write each edge as (u→v, w). Decide whether edges are directed."

Set start vertex s

2) Choose source

Identify the required source in the question; set dist[s]=0."

Set up dist and parent

3) Initialize

dist[]=∞ except dist[s]=0; parent[]=NIL."

Pop min dist + relax outgoing edges

4) Relax systematically

Use a priority queue (or a manual min-table for small graphs)."

Final distances + shortest paths

5) Produce output

dist[] gives shortest costs; parent[] reconstructs paths."

Algorithm: Dijkstra for SSSP (Nonnegative weights)

This algorithm maintains:

dist: current best distances from $s$
parent: used to reconstruct the shortest path tree
A set of processed vertices, often via a priority queue

Dijkstra pseudocode (conceptual)

Initialize all $\text{dist}[x]=\infty$ ; set $\text{dist}[s]=0$ .
While there are unprocessed vertices:
- Pick $u$ with minimum $\text{dist}[u]$ .
- For each outgoing neighbor $v$ of $u$ , relax edge $(u,v)$ .
After termination, $\text{dist}[v]$ is the shortest distance from $s$ to $v$ .

Complexity (why priority queue matters)

With a binary heap priority queue, typical complexity is:

O\big((V+E)\log V\big),

where $V$ is the number of vertices and $E$ the number of edges.

Step-by-step: Apply Dijkstra to your (image) graph

1
Step 1
List every edge (u→v) with its weight w. If the graph is undirected, include both (u→v,w) and (v→u,w).
2
Step 2
Let s be the given starting vertex. Set dist[s]=0 and dist[others]=∞.
3
Step 3
Set parent[*]=NIL. When relaxation improves dist[v], store parent[v]=u.
4
Step 4
Maintain a table/notes of dist values and parent updates per extraction of u.
5
Step 5
Repeatedly pick the unprocessed vertex u with smallest dist[u]. Mark u as processed.
6
Step 6
For each edge (u→v,w): compute candidate = dist[u] + w. If candidate < dist[v], set dist[v]=candidate and parent[v]=u.
7
Step 7
At the end, dist[*] are final shortest distances from s.
8
Step 8
To recover the shortest path s→t, follow parent pointers backwards from t until reaching s, then reverse the sequence.

Working template (fill this for your exact graph)

Use this structure to compute shortest paths. Replace vertices/edges with those from the image.

Distance initialization template

Assume vertices $V=\{v_1,\dots,v_n\}$ and source $s=v_1$ .

Vertex	dist (start)	parent (start)
$s$	0	NIL
Others	$\infty$	NIL

Iteration log template

At each iteration k, you:

extract $u_k$ with minimum dist
relax each outgoing edge from $u_k$

Iteration k	Extract u	Relax edge (u→v,w)	candidate dist[v]	Updated?
1	u₁	(u₁→v, w)	dist[u₁]+w	Yes/No
2	u₂
…	…

Final output format

When finished, you should report:

shortest distance from $s$ to every vertex $t$
the actual path using parent pointers

Example reporting format (template):

$d(s,a)=\dots$ with path $s \to \dots \to a$
$d(s,b)=\dots$ with path $s \to \dots \to b$

Graph concept map (what happens internally)

Common pitfalls and checks

Final distances from source (fill with your results)

After running Dijkstra, dist[t] for each vertex t becomes the data.

SSSP Quick Self-Check

1 / 4

Question · Term

What is relaxation?

Click to reveal

Answer · Definition

Attempt to improve dist[v] using an edge (u→v): if dist[u]+w(u,v) < dist[v], update dist[v] and parent[v]=u.

Knowledge Check

Question 1 of 4

Q1Single choice

Dijkstra’s algorithm is guaranteed to produce correct shortest paths when the graph has which property?

All edge weights are nonnegative

All edge weights are negative

Edge weights may be negative as long as there is no cycle

The graph must be a tree

Explore Related Topics

Hamiltonian Path: Existence and How to Decide (Graph-Theoretic Method)

Minimum Spanning Trees: Concept, Prim’s vs. Kruskal’s, and Complexity Analysis

State the graph coloring problem and write the algorithm. Apply backtracking technique to solve the 3-colouring problem for the following graph. ![image](https://9lrt4yspyx.ufs.sh/f/z1z03jdN1p04sDZHdx0RokTQjiuapSXvByEJLFr8weIGhWCq)

Browse all research articles