**The single-source shortest path problem is about finding the paths between a given vertex(called the source) to all the other vertices(called the destination) in a graph such that the total distance between them is minimum.**

Dijkstra’s algorithm is an algorithm for finding the shortest path between any two nodes of a given graph. While traversing the shortest path between two nodes, it is not necessary that every node will be visited.

Dijkstra’s algorithm can be used to solve the SSSP problem for weighted graphs. In the above example, the shortest path between the vertices V5 and V3 is numerically weighted 8(V5 -> V4 -> V3).

Dijkstra’s Algorithm finds use in various real-life applications:

- Digital Mapping Services
- Social Networking Applications
- Telephone Network
- IP Routing to find the shortest path

**Table of Contents**

### Creation of Graph

To implement the Graph data structure, we first initialize the “Graph” class. Then, we overwrite the __init__ function and create another function to add weighted edges between the newly added nodes.

```
#Initializing the Graph Class
class Graph:
def __init__(self):
self.nodes = set()
self.edges = defaultdict(list)
self.distances = {}
def addNode(self,value):
self.nodes.add(value)
def addEdge(self, fromNode, toNode, distance):
self.edges[fromNode].append(toNode)
self.distances[(fromNode, toNode)] = distance
```

### Implementation of Dijkstra’s Algorithm to solve SSSP Problem

To implement Dijkstra’s algorithm in python, we create the `dijkstra`

method which takes two parameters – the graph under observation and the initial node which will be the source point for our algorithm.

Dijkstra’s algorithm is based on the following steps:

- We will receive a weighted graph and an initial node.
- Start with the initial node. Check the adjacent nodes.
- Find the node with the minimum edge value.
- Repeat this process until the destination node is visited.
- At the end of the function, we return the shortest path weight for each node and the path as well.

```
#Implementing Dijkstra's Algorithm
def dijkstra(graph, initial):
visited = {initial : 0}
path = defaultdict(list)
nodes = set(graph.nodes)
while nodes:
minNode = None
for node in nodes:
if node in visited:
if minNode is None:
minNode = node
elif visited[node] < visited[minNode]:
minNode = node
if minNode is None:
break
nodes.remove(minNode)
currentWeight = visited[minNode]
for edge in graph.edges[minNode]:
weight = currentWeight + graph.distances[(minNode, edge)]
if edge not in visited or weight < visited[edge]:
visited[edge] = weight
path[edge].append(minNode)
return visited, path
customGraph = Graph()
customGraph.addNode("A")
customGraph.addNode("B")
customGraph.addNode("C")
customGraph.addNode("D")
customGraph.addNode("E")
customGraph.addNode("F")
customGraph.addNode("G")
customGraph.addEdge("A", "B", 2)
customGraph.addEdge("A", "C", 5)
customGraph.addEdge("B", "C", 6)
customGraph.addEdge("B", "D", 1)
customGraph.addEdge("B", "E", 3)
customGraph.addEdge("C", "F", 8)
customGraph.addEdge("D", "E", 4)
customGraph.addEdge("E", "G", 9)
customGraph.addEdge("F", "G", 7)
print(dijkstra(customGraph, "A"))
#Output
({'A': 0, 'B': 2, 'C': 5, 'D': 3, 'E': 5, 'G': 14, 'F': 13},
defaultdict(<class 'list'>,
{'B': ['A'], 'C': ['A'], 'D': ['B'], 'E': ['B'], 'G': ['E'], 'F': ['C']}))
```

#### Time and Space Complexity

The time complexity for Dijkstra’s algorithm is **O(V^2)** where “V” is the number of vertices of the graph. This is due to the fact that we have used two loops nested together and each of them iterates over all the nodes.

The space complexity is **O(E)** where “E” is the number of edges of the graph because we are appending `path`

with the edges.