# 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.

## Comments

## Post a Comment

Leave Comment