Example graph

In the world of algorithms, graph algorithms have broad applications—especially in pathfinding and optimization problems. In the previous tutorial, we compared advanced sorting algorithms; in this one, we delve deeply into two graph algorithms: Dijkstra’s algorithm and A* algorithm. Both are designed to find the shortest path between two nodes in a graph—but they differ significantly in implementation mechanics and applicable scenarios.

Dijkstra’s Algorithm

Dijkstra’s algorithm is a greedy algorithm that computes the shortest paths from a single source node to all other nodes in a weighted graph with non-negative edge weights. Its core idea is to iteratively select the unvisited node with the smallest known distance from the source, then relax (i.e., update) distances to its neighbors.

Algorithm Steps

1. Initialization: Set the distance to the start node as 0, and all other nodes’ distances as ∞.
2. Mark all nodes as unvisited.
3. Among unvisited nodes, select the one u with the smallest current distance from the start.
4. For each neighbor v of u, compute the tentative distance from the start to v via u. If this distance is smaller than v’s current distance, update v’s distance.
5. Mark u as visited.
6. Repeat steps 3–5 until all nodes are visited—or until the target node is reached.

Time Complexity

The time complexity of Dijkstra’s algorithm is $O((V + E) \log V)$, where $V$ is the number of vertices and $E$ is the number of edges. Using a priority queue (e.g., a min-heap) ensures efficient extraction of the minimum-distance node.

Case Study

Consider the following simple weighted undirected graph:

       1
   (A)----(B)
    | \    |
   4|  \2  |1
    |   \  |
   (C)----(D)
       3

We want the shortest path from node A to node D.

1. Initialization: d(A) = 0, d(B) = ∞, d(C) = ∞, d(D) = ∞.
2. Select A:
   • d(B) = min(∞, 0 + 1) = 1
   • d(C) = min(∞, 0 + 4) = 4

Select B:

• d(D) = min(∞, 1 + 1) = 2

Select D: no unvisited neighbors remain → terminate.

Shortest path: A → B → D, total distance = 2.

Python Implementation

import heapq

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

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

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# Example graph
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'D': 1},
    'C': {'A': 4, 'D': 3},
    'D': {'B': 1, 'C': 3}
}

print(dijkstra(graph, 'A'))  # Output shortest distances from A to all nodes

A* Algorithm

A* is an informed search algorithm that extends Dijkstra’s algorithm by incorporating a heuristic function to guide the search toward the goal more efficiently. It balances actual path cost (g) and estimated remaining cost (h) to prioritize promising paths.

Heuristic Function

The heuristic function h(n) estimates the cost from node n to the goal. Common choices include:

• Manhattan distance, suitable for grid-based movement with 4-directional constraints.
• Euclidean distance, appropriate for continuous or diagonal movement.

Crucially, for A* to guarantee optimality, h(n) must be admissible (never overestimate the true cost) and consistent (satisfy the triangle inequality).

Algorithm Steps

1. Initialize: For the start node, set g = 0 (actual cost from start), h = heuristic(start, goal), and f = g + h.
2. Maintain an open set (nodes to be evaluated) and a closed set (nodes already evaluated).
3. Select the node in the open set with the lowest f value; remove it and process it.
4. For each unvisited neighbor:
   • Compute its tentative g (via current node).
   • If better, update its g, h, and f, and add it to the open set.
5. Repeat until the goal is reached—or the open set is empty.

Case Study

Reusing the same graph, with goal D, and assuming a simple heuristic h(X) = |ord(X) - ord('D')| (character ASCII difference):

1. Start at A:
   • g(A) = 0, h(A) = |65 − 68| = 3, f(A) = 3
2. Expand A:
   • B: g = 1, h = |66 − 68| = 2, f = 3
   • C: g = 4, h = |67 − 68| = 1, f = 5
3. Choose B (tie-breaking arbitrarily; both A and B have f = 3).
   • From B, reach D: g(D) = 1 + 1 = 2, h(D) = 0, f(D) = 2 → goal found.

Note: With a better heuristic (e.g., geometric or domain-specific), A* would prune more aggressively than Dijkstra.

Python Implementation

def heuristic(a, b):
    # Manhattan-like heuristic based on character ASCII values
    return abs(ord(a) - ord(b))

def a_star(graph, start, goal):
    open_list = []
    closed_set = set()
    g_score = {vertex: float('infinity') for vertex in graph}
    g_score[start] = 0
    f_score = {vertex: float('infinity') for vertex in graph}
    f_score[start] = heuristic(start, goal)
    heapq.heappush(open_list, (f_score[start], start))

    while open_list:
        current = heapq.heappop(open_list)[1]

        if current == goal:
            return g_score[current]  # Return shortest path cost to goal

        closed_set.add(current)

        for neighbor, weight in graph[current].items():
            if neighbor in closed_set:
                continue

            tentative_g_score = g_score[current] + weight

            if tentative_g_score < g_score[neighbor]:
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)
                heapq.heappush(open_list, (f_score[neighbor], neighbor))

    return float('infinity')  # No path exists

# Example usage
print(a_star(graph, 'A', 'D'))  # Returns 2