CQH103: Graph Algorithms – Dijkstra’s Algorithm and Finding the Shortest Path

What do GPS apps, social networks, and game level maps all have in common? They all rely on graphs to represent and navigate complex relationships. Graph algorithms allow us to model and solve real-world problems that involve connections, paths, and decisions.

One of the most powerful tools in this space is Dijkstra’s Algorithm—used to find the shortest path between points in a weighted graph.

In this post, we’ll explore how graphs work, how Dijkstra’s Algorithm solves pathfinding problems, and how it relates to big challenges like the Traveling Salesman Problem.

What is a Graph?

A graph is a collection of nodes (or vertices) and edges connecting them. Edges can be:

  • Directed (one-way)
  • Undirected (two-way)
  • Weighted (cost or distance between nodes)

Graphs can model:

  • Roads between cities
  • Friend connections on a social network
  • Dependencies between tasks in a project

Python Representation

Graphs are often represented using an adjacency list:

graph = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
    'D': {'B': 1, 'C': 4, 'E': 3},
    'E': {'C': 8, 'D': 3}
}

Dijkstra’s Algorithm – Finding the Shortest Path

Dijkstra’s Algorithm finds the shortest path from a starting node to all other nodes in a weighted graph.

How It Works

  1. Start with a distance of 0 to the start node and infinity to all others.
  2. Visit the closest unvisited node.
  3. Update the distances to its neighbors.
  4. Mark it as visited.
  5. Repeat until all nodes are visited or the shortest path is found.

Python Example (Simplified)

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

Why It Matters

Dijkstra’s Algorithm powers:

  • GPS navigation – Find the fastest or shortest route.
  • Network routing – Data packet delivery.
  • Game AI – Move characters or objects across maps efficiently.

It’s also a stepping stone to more advanced pathfinding methods like A*, which we’ll explore later.

The Traveling Salesman Problem (TSP)

While Dijkstra finds the shortest path from one node, the Traveling Salesman Problem asks:

“What is the shortest possible route that visits each city exactly once and returns to the starting point?”

TSP is much harder—it’s an NP-hard problem, meaning we don’t have an efficient way to solve it perfectly for large datasets.

Still, we can use Dijkstra or similar shortest path algorithms to build heuristics or approximations to get “good enough” solutions.

Real-World TSP Uses

  • Delivery route optimization
  • Circuit board design
  • Drone and robot path planning

Data Structures Behind the Scenes

Dijkstra’s efficiency depends heavily on using the right data structures:

  • A priority queue (usually a binary heap) for selecting the next node
  • A graph stored in an adjacency list or matrix

Choosing the right structure keeps the algorithm fast and memory-efficient. Another great example of algorithms and data structures working hand-in-hand.

Challenge Time! 🧠

  • Modify the Dijkstra example to print the shortest path from the start node to a target node (not just the distance).
  • Try implementing Dijkstra on a grid (2D map) instead of a named node graph.

Next up in CQH103: Smarter pathfinding with A*—perfect for games, maps, and AI! 🚀