Foundations — Dijkstra's algorithm — greedy, priority queue, O((V+E) log V) — no negative edges

This page builds the vocabulary the parent note Dijkstra's algorithm leans on, one symbol at a time. Nothing below assumes you have seen graph notation before. Read top to bottom; each idea is the ground the next one stands on.

1. What is a graph? ($G$, $V$, $E$)

Look at the figure below. Each labelled circle is a vertex. Each arrow between two circles is an edge.

1b. Counting the dots and lines — $|V|$ and $|E|$

The same letters $V$ and $E$ get reused in two different jobs, and mixing them up trips beginners. Let's separate them cleanly.

2. Naming individual dots — the placeholders $u$ and $v$

Before we can talk about one specific dot or the road between two dots, we need short names for "some dot." Just as algebra uses $x$ for "some number," graph work uses lowercase letters for "some vertex."

3. Direction — arrows vs. plain lines

An edge can point one way (a one-way street) or both ways (a two-way street). We use the placeholders $u$ and $v$ from §2 to describe the two endpoints.

The parent's worked example (A→B, A→C, ...) uses arrows, so it is a directed graph. In the figure of §1, notice A→B exists but there is no B→A.

4. Weights — putting a cost on each edge ($w(u,v)$)

Read $w(u,v)$ out loud as "the cost of the road from $u$ to $v$." The figure below puts a yellow number on every road of the parent's example graph.

Follow the picture: the edge A→C carries the yellow label $1$, so $w(A,C)=1$; the edge A→B carries $4$, so $w(A,B)=4$; and so on for all five arrows. The green note at the top of the figure highlights the punchline we prove next — the two-hop route A→C→B (cost $1+2=3$) is cheaper than the single road A→B (cost $4$).

5. The source $s$ — where every journey starts

Before we talk about a path, we need to name the one place all journeys begin from.

In the parent's worked example the source is $s=A$: every distance is measured starting from A.

6. A path, and how its weights add up

Now — what does it cost to walk a path? We already have $w(u,v)$ for one edge. A path is several edges in a row, so we simply add the edge-weights together, one per step.

Reading the squiggle $s⇝u$

7. The true distance $\delta (v)$, and infinity $\infty$

$\delta (v)={\min }_{\text{all paths }s⇝v}(\text{weight}(P))$

The $\min$ symbol means "take the smallest." So $\delta (v)$ is the smallest possible path-weight (using the sum from §6) — by definition, no route beats it.

8. The tentative distance $dist[v]$ — our shrinking guess

Here is the subtle one. $\delta (v)$ is the true answer we don't know yet. $dist[v]$ is our current best guess, which we improve over time until it equals $\delta (v)$.

The figure below shows all four boxes of the parent example. The red row is the starting guess (everything $\infty$ except $A=0$); the green row is the final answer, where each $dist[v]$ has shrunk down until it equals $\delta (v)$.

Trace the vertical arrows in the picture: box $B$ falls from $\infty$ to $3$, box $C$ from $\infty$ to $1$, box $D$ from $\infty$ to $4$, while box $A$ stays pinned at $0$. Each downward drop is one relaxation, defined next.

9. Relaxation — the one update rule

The $+$ here is exactly the path-sum of §6: "cost already paid to reach $u$" plus "one more edge $w(u,v)$." The arrow $\leftarrow$ means "becomes" — the left box is overwritten with the right value (it is assignment, not equality).

10. The priority queue (min-heap)

Dijkstra fills this bucket with pairs (dist[v], v) — "guessed cost, vertex" — and always pulls out the vertex with the smallest guessed cost next. That "always grab the nearest unfinished dot" is the greedy heart. See Priority Queue (Binary Heap) for how the bucket works internally.

11. Big-O notation — $O(\cdot )$ — and where $(V+E)\log V$ comes from

$\log |V|$ (logarithm) answers "how many times can I halve $|V|$ before reaching $1$?" — it's the depth of the heap, hence the cost of one pop or push. Tiny even for huge $|V|$.

Prerequisite map

Each foundation feeds the next: dots and lines carry weights; weights summed along a path give the true distance; guesses chase that truth via relaxation; the heap orders the chase; non-negativity makes the greedy order safe. Read the diagram below top to bottom — an arrow "X → Y" means "you need X before Y makes sense."

Equipment checklist

Connections

• The parent topic (Hinglish)
• BFS — the all-weights-equal-1 special case of everything above
• Priority Queue (Binary Heap) — the min-heap engine defined in §10
• Greedy algorithms — why "grab the nearest unfinished dot" is justified
• Bellman-Ford algorithm — what to use when §4's non-negative rule is broken