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