The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Shortest Path Algorithms

Next ►
►

Introduction

Shortest path algorithms are fundamental in graph theory and have numerous applications in various fields such as network routing, geographical mapping, and logistics. This section will cover the essential algorithms used to find the shortest path in a graph, including Dijkstra's algorithm, Bellman-Ford algorithm, and the A* search algorithm.

Key Concepts and Notation

Before diving into the algorithms, let's define some basic concepts and notation:

  • Graph (G): A set of vertices (V) and edges (E) connecting pairs of vertices.
  • Weighted Graph: A graph where each edge has a numerical value (weight) associated with it.
  • Path: A sequence of edges that connect a sequence of vertices.
  • Shortest Path: The path between two vertices that has the smallest sum of edge weights.

Dijkstra's Algorithm

Dijkstra's algorithm is used to find the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative weights.

Steps of Dijkstra's Algorithm

  1. Initialization:

    • Set the distance to the source vertex to 0 and to all other vertices to infinity.
    • Mark all vertices as unvisited. Create a set of all the unvisited vertices called the unvisited set.

  2. Visit the unvisited vertex with the smallest distance:

    • For the current vertex, consider all its unvisited neighbors and calculate their tentative distances through the current vertex.
    • Compare the newly calculated tentative distance to the current assigned value and assign the smaller one.
    • After considering all neighbors of the current vertex, mark the current vertex as visited. A visited vertex will not be checked again.

  3. Repeat:

    • Continue this process until all vertices are visited or the smallest distance among the unvisited vertices is infinity.

Example

Consider the following graph:

    A
   / \
  1   4
 /     \
B---2---C
 \     /
  3   1
   \ /
    D
  • Vertices: A, B, C, D
  • Edges: (A-B, 1), (A-C, 4), (B-C, 2), (B-D, 3), (C-D, 1)

Let's find the shortest path from A to all other vertices.

import heapq

def dijkstra(graph, start):
    # Initialize distances and priority queue
    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)
        
        # Nodes can get added to the priority queue multiple times. We only process a vertex the first time we remove it from the priority queue.
        if current_distance > distances[current_vertex]:
            continue
        
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            
            # Only consider this new path if it's better
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

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

print(dijkstra(graph, 'A'))

Explanation

  • Initialization: Set distances to infinity, except for the start vertex A which is set to 0.
  • Priority Queue: Use a priority queue to always expand the vertex with the smallest known distance.
  • Relaxation: Update the distances to neighboring vertices if a shorter path is found.

Bellman-Ford Algorithm

The Bellman-Ford algorithm is used to find the shortest paths from a single source vertex to all other vertices in a weighted graph. Unlike Dijkstra's algorithm, Bellman-Ford can handle graphs with negative weights.

Steps of Bellman-Ford Algorithm

  1. Initialization:

    • Set the distance to the source vertex to 0 and to all other vertices to infinity.

  2. Relaxation:

    • For each edge, update the distance to the destination vertex if the path through the source vertex is shorter.

  3. Repeat:

    • Repeat the relaxation step for |V| - 1 times, where |V| is the number of vertices.

  4. Check for Negative Cycles:

    • Perform one more relaxation step. If any distance is updated, a negative cycle exists.

Example

Consider the same graph but with a negative weight:

    A
   / \
  1   4
 /     \
B---2---C
 \     /
  3   -5
   \ /
    D
def bellman_ford(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    
    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor, weight in graph[vertex].items():
                if distances[vertex] + weight < distances[neighbor]:
                    distances[neighbor] = distances[vertex] + weight
    
    # Check for negative weight cycles
    for vertex in graph:
        for neighbor, weight in graph[vertex].items():
            if distances[vertex] + weight < distances[neighbor]:
                raise ValueError("Graph contains a negative weight cycle")
    
    return distances

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

print(bellman_ford(graph, 'A'))

Explanation

  • Initialization: Set distances to infinity, except for the start vertex A which is set to 0.
  • Relaxation: Update the distances to neighboring vertices if a shorter path is found.
  • Negative Cycle Check: Ensure no negative weight cycles exist by performing an additional relaxation step.

A* Search Algorithm

The A* search algorithm is used to find the shortest path from a start vertex to a goal vertex in a weighted graph. It uses heuristics to improve the efficiency of the search.

Steps of A* Search Algorithm

  1. Initialization:

    • Set the distance to the start vertex to 0 and to all other vertices to infinity.
    • Use a priority queue to store vertices to be explored, prioritized by the estimated total cost (distance + heuristic).

  2. Visit the vertex with the smallest estimated total cost:

    • For the current vertex, consider all its neighbors and calculate their tentative distances through the current vertex.
    • Update the priority queue with the new estimated total cost.

  3. Repeat:

    • Continue this process until the goal vertex is reached or the priority queue is empty.

Example

Consider the following graph with heuristic values:

    A
   / \
  1   4
 /     \
B---2---C
 \     /
  3   1
   \ /
    D

Heuristic values (h) to goal vertex D:

  • h(A) = 3
  • h(B) = 2
  • h(C) = 1
  • h(D) = 0
import heapq

def a_star(graph, start, goal, heuristic):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0 + heuristic[start], start)]
    
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        
        if current_vertex == goal:
            return distances[goal]
        
        for neighbor, weight in graph[current_vertex].items():
            distance = distances[current_vertex] + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance + heuristic[neighbor], neighbor))
    
    return float('infinity')

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

heuristic = {
    'A': 3,
    'B': 2,
    'C': 1,
    'D': 0
}

print(a_star(graph, 'A', 'D', heuristic))

Explanation

  • Initialization: Set distances to infinity, except for the start vertex A which is set to 0.
  • Priority Queue: Use a priority queue to always expand the vertex with the smallest estimated total cost.
  • Heuristic: Use heuristic values to guide the search towards the goal vertex.

Practical Exercises

Exercise 1: Implement Dijkstra's Algorithm

Given the following graph, implement Dijkstra's algorithm to find the shortest path from vertex 'S' to all other vertices.

    S
   / \
  7   9
 /     \
A---10--B
 \     /
  4   2
   \ /
    C

Solution

graph = {
    'S': {'A': 7, 'B': 9},
    'A': {'S': 7, 'B': 10, 'C': 4},
    'B': {'S': 9, 'A': 10, 'C': 2},
    'C': {'A': 4, 'B': 2}
}

print(dijkstra(graph, 'S'))

Exercise 2: Implement Bellman-Ford Algorithm

Given the following graph with a negative weight, implement the Bellman-Ford algorithm to find the shortest path from vertex 'S' to all other vertices.

    S
   / \
  7   9
 /     \
A---10--B
 \     /
  4   -2
   \ /
    C

Solution

graph = {
    'S': {'A': 7, 'B': 9},
    'A': {'S': 7, 'B': 10, 'C': 4},
    'B': {'S': 9, 'A': 10, 'C': -2},
    'C': {'A': 4, 'B': -2}
}

print(bellman_ford(graph, 'S'))

Exercise 3: Implement A* Search Algorithm

Given the following graph and heuristic values, implement the A* search algorithm to find the shortest path from vertex 'S' to vertex 'C'.

    S
   / \
  7   9
 /     \
A---10--B
 \     /
  4   2
   \ /
    C

Heuristic values (h) to goal vertex C:

  • h(S) = 5
  • h(A) = 3
  • h(B) = 2
  • h(C) = 0

Solution

graph = {
    'S': {'A': 7, 'B': 9},
    'A': {'S': 7, 'B': 10, 'C': 4},
    'B': {'S': 9, 'A': 10, 'C': 2},
    'C': {'A': 4, 'B': 2}
}

heuristic = {
    'S': 5,
    'A': 3,
    'B': 2,
    'C': 0
}

print(a_star(graph, 'S', 'C', heuristic))

Conclusion

In this section, we explored three fundamental shortest path algorithms: Dijkstra's algorithm, Bellman-Ford algorithm, and A* search algorithm. Each algorithm has its strengths and is suitable for different types of graphs and applications. Understanding these algorithms and their implementations is crucial for solving complex graph-related problems efficiently.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2024. All rights reserved