Python: Shortest Path in Weighted Graph

1. Introduction

Graphs are fundamental data structures used to represent network-like structures. In weighted graphs, each edge has an associated weight or cost. The challenge is to find the shortest path between two nodes in such a graph. Dijkstra's algorithm is a well-known solution to this problem. In this post, we will implement and understand Dijkstra's algorithm.

2. Program Overview

1. Define the Graph class.

2. Implement the method to add vertices and edges.

3. Implement Dijkstra's algorithm to find the shortest path.

4. Demonstrate the program using a sample weighted graph.

3. Code Program

class Graph:
    def __init__(self):
        self.vertices = {}

    def add_vertex(self, name, edges):
        """Add a vertex and its associated edges to the graph."""
        self.vertices[name] = edges

    def shortest_path(self, start, end):
        """Find the shortest path using Dijkstra's algorithm."""
        shortest_paths = {vertex: (float('infinity'), None) for vertex in self.vertices}
        current_distance = 0
        current_vertex = start

        while current_vertex != end:
            for neighbour, weight in self.vertices[current_vertex].items():
                new_distance = current_distance + weight
                if new_distance < shortest_paths[neighbour][0]:
                    shortest_paths[neighbour] = (new_distance, current_vertex)

            next_destinations = {vertex: shortest_paths[vertex] for vertex in self.vertices.keys()
                                 if vertex not in shortest_paths}
            if not next_destinations:
                return "Path not found."
            current_vertex = min(next_destinations, key=lambda k: next_destinations[k][0])
            current_distance = shortest_paths[current_vertex][0]

        path = []
        while current_vertex:
            path.append(current_vertex)
            next_vertex = shortest_paths[current_vertex][1]
            current_vertex = next_vertex
        return path[::-1]

# Sample graph
g = Graph()
g.add_vertex('A', {'B': 1, 'C': 4})
g.add_vertex('B', {'A': 1, 'C': 2, 'D': 5})
g.add_vertex('C', {'A': 4, 'B': 2, 'D': 1})
g.add_vertex('D', {'B': 5, 'C': 1})
print("Shortest path from A to D:", g.shortest_path('A', 'D'))

Output:

Shortest path from A to D: ['A', 'B', 'C', 'D']

4. Step By Step Explanation

1. We initiate the graph with vertices. Each vertex has a dictionary representing its edges and their weights.

2. The add_vertex method allows us to add vertices and their respective edges.

3. The core of the program is the shortest_path method which uses Dijkstra's algorithm:

• We initialize shortest paths to all vertices as infinity except the starting vertex.
• At every step, we pick the vertex with the shortest distance.
• We update the shortest paths for its neighboring vertices.
• We continue this process until we reach the end vertex.

4. The resulting shortest path is determined by backtracking from the end vertex to the start using the stored paths.