Skip to content

Dijkstra Algorithm

Understanding weighted graph pathfinding and cheapest-route calculation (used on the fly-in project).

1️⃣ What is Dijkstra?

Dijkstra is a graph algorithm used to:

  • find cheapest paths
  • calculate weighted routes
  • optimize movement cost
  • solve weighted graph problems

Focuses on:

lowest total cost

NOT:

fewest movements

2️⃣ Weighted Graphs

A weighted graph means:

connections or zones have different costs

Example

normal      = 1
priority    = 1
restricted  = 2
blocked     = impossible

This means:

not all paths cost the same

3️⃣ Cheapest Path vs Shortest Path

BFS thinks:

fewest steps

Dijkstra thinks:

lowest total cost

Example

Path A

start -> restricted -> goal

Cost:

3 turns

Path B

start -> normal -> normal -> goal

Cost:

3 turns

Path C

start -> priority -> goal

Cost:

2 turns

Dijkstra chooses:

Path C

because:

lowest total cost

4️⃣ Priority Queue (heapq)

Dijkstra usually uses:

import heapq

because it constantly needs:

cheapest current node

Example

queue = []

heapq.heappush(queue, (1, "A"))
heapq.heappush(queue, (5, "B"))
heapq.heappush(queue, (2, "C"))

heapq automatically organizes:

lowest cost first

Then:

heapq.heappop(queue)

returns:

(1, "A")

5️⃣ Cost Tracking

Dijkstra stores:

best known cost for every node

Example

costs = {
    "start": 0,
    "A": 1,
    "B": 4,
    "goal": 2
}

Core Idea

If a cheaper route is discovered:

update cost

6️⃣ Parent Tracking

Dijkstra also stores:

where each node came from

This allows:

path reconstruction

Example

parents = {
    "A": "start",
    "goal": "A"
}

7️⃣ Visited Nodes

Dijkstra tracks visited nodes to avoid:

  • unnecessary processing
  • loops
  • recalculating explored routes

Example

visited = {
    "start",
    "A"
}

8️⃣ Dijkstra Logic

Dijkstra works by constantly exploring:

The currently cheapest known route

The algorithm starts at the initial node and gradually expands through the graph.

Every time it discovers a cheaper route to a node:

  • the cost is updated
  • the route information is updated
  • the node becomes a better candidate for exploration

Core Concepts

Cheapest-first exploration

Unlike BFS, Dijkstra does not explore based on:

arrival order

Instead, it explores based on:

lowest total cost

Continuous optimization

The algorithm constantly compares:

old path cost
vs
new possible path cost

If the new route is cheaper:

replace old cost

Progressive expansion

Dijkstra gradually expands through the graph:

start
 ↓
cheap neighbors
 ↓
slightly more expensive neighbors
 ↓
more expensive neighbors

The graph is explored in order of increasing total cost.

Weighted movement

This is why Dijkstra is extremely useful for:

  • traffic systems
  • GPS navigation
  • weighted movement games
  • drone routing
  • path optimization

9️⃣ Path Reconstruction

Once the goal is reached:

walk backwards using parents

Example

goal
 ↑
A
 ↑
start

Reverse result:

start -> A -> goal

🔟 Visual Example

Graph:

        start
       /     \
     (1)     (5)
     A         B
      \
      (1)
        \
        goal

Exploration

Dijkstra sees:

A = cost 1
B = cost 5

It explores:

A first

because:

1 < 5

Final Path

start -> A -> goal

Total cost:

2

1️⃣1️⃣ Fly-in Connection

Fly-in is essentially:

weighted graph pathfinding

because:

  • movement costs exist
  • restricted zones cost more
  • blocked zones are invalid
  • drones need optimized routes

Dijkstra fits Fly-in because it:

  • minimizes total movement cost
  • avoids blocked zones
  • supports weighted routing
  • generates optimal paths

1️⃣2️⃣ BFS vs Dijkstra

BFS

Explores:

fewest steps

Uses:

deque

Dijkstra

Explores:

lowest cost path

Uses:

heapq

BFS

Good for:

  • unweighted graphs
  • same movement costs

Dijkstra

Good for:

  • weighted graphs
  • route optimization
  • movement costs

1️⃣3️⃣ Complexity

Typical Dijkstra complexity:

O((V + E) log V)

Where:

V = vertices
E = edges

Why more expensive than BFS?

Because:

heapq sorting adds extra work

BUT:

weighted pathfinding requires it

1️⃣4️⃣ Mental Model

Think of Dijkstra like:

GPS route optimization

The algorithm constantly asks:

"What is currently the cheapest route?"

NOT:

"What was explored first?"

Final Mental Image

BFS

Closest room first

Dijkstra

Cheapest road first