## What is Dijkstra Algorithm?

The Dijkstra Algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights. The algorithm is named after its discoverer, Dutch computer scientist Edsger W. Dijkstra.

## Features of dijkstra algorithm

• It is a greedy algorithm that finds the shortest path from a starting node to all other nodes in a graph.
• It uses a priority queue to keep track of the nodes that have been visited and the shortest distance to them.
• It is not guaranteed to find the shortest path if there are multiple shortest paths.
• It guarantees to find the shortest path from a given starting node to all other nodes in the graph, given that the graph does not contain any negative weight cycles.

## Examples of dijkstra algorithm

### 1. Find the shortest path from node A to node B in a graph.

``````def dijkstra(graph, A, B):
# create a set of visited nodes
visited = set()
# create a set of nodes to be visited
unvisited = set(graph.keys())
# create a dictionary of distances
distance = {}
# create a dictionary of predecessors
predecessor = {}
# assign the distance from A to A to be 0
distance[A] = 0
# assign the predecessor of A to be None
predecessor[A] = None
# while there are unvisited nodes
while unvisited:
# find the node with the smallest distance in the set of unvisited nodes
current = min(unvisited, key=lambda k: distance[k])
# remove the node from the set of unvisited nodes
unvisited.remove(current)
# if the distance of the current node is infinity, there is no path to the end node
if distance[current] == float('inf'):
break
# for each neighbor of the current node
for neighbor in graph[current]:
# if the neighbor is not visited
if neighbor not in visited:
# if the distance to the neighbor is greater than the distance to the current node plus the edge weight
if distance[neighbor] > distance[current] + graph[current][neighbor]:
# update the distance to the neighbor
distance[neighbor] = distance[current] + graph[current][neighbor]
# update the predecessor of the neighbor
predecessor[neighbor] = current
# add the current node to the set of visited nodes
# if the distance to the end node is infinity, there is no path to the end node
if distance[B] == float('inf'):
return None
# create a list of nodes that are on the shortest path from the start node to the end node
path = []
# set the current node to be the end node
current = B
# while the current node has a predecessor
while current:
# add the current node to the list of nodes
path.append(current)``````

### 2. Find the shortest path from node A to all other nodes in a graph.

``````def dijkstra(graph, start):
# initialize the distance to start node to 0
distance = {start: 0}
# initialize the set of visited nodes to empty
visited = set()
# initialize the set of unvisited nodes to all nodes in the graph
unvisited = set(graph.keys())
# while there are unvisited nodes
while unvisited:
# find the node with the smallest distance in the set of unvisited nodes
current = min(unvisited, key=lambda x: distance[x])
# add the node to the set of visited nodes
# remove the node from the set of unvisited nodes
unvisited.remove(current)
# for each node in the current node's adjacency list
for neighbor in graph[current]:
# if the distance to the neighbor is infinite
if neighbor not in distance:
# set the distance to the neighbor to the distance to the current node plus the edge weight
distance[neighbor] = distance[current] + graph[current][neighbor]
# return the distance dictionary
return distance``````

### 3. Find the shortest path from node A to node B in a weighted graph.

``````def dijkstra(graph, start, goal):
# keep track of all the nodes
nodes = [start]
# keep track of all the paths
paths = {start: [start]}
# keep track of all the shortest paths
shortest_paths = {start: 0}
# keep track of all the shortest paths
visited = set()
# keep looping until all the nodes have been visited
while nodes:
# sort the nodes
nodes.sort(key=lambda x: shortest_paths[x])
# get the first node
current_node = nodes.pop(0)
# check if the current node is the goal
if current_node == goal:
return paths[current_node]
# check if the current node has already been visited
if current_node in visited:
continue
# get the neighbors of the current node
neighbors = graph[current_node]
# loop over the neighbors
for neighbor in neighbors:
# get the edge weight
edge_weight = neighbors[neighbor]
# get the total distance from the start node to the neighbor
total_distance = shortest_paths[current_node] + edge_weight
# check if the neighbor has already been visited
if neighbor in visited:
continue
# check if the current neighbor is already in the shortest paths
if neighbor not in shortest_paths or total_distance < shortest_paths[neighbor]:
# add the neighbor to the shortest paths
shortest_paths[neighbor] = total_distance
# add the neighbor to the paths
paths[neighbor] = paths[current_node] + [neighbor]
# mark the current node as visited
# return an empty list if there is no path
return []``````

### 4. Find the shortest path from node A to all other nodes in a weighted graph.

``````def dijkstra(graph, start):
# create a set of nodes not yet evaluated
unvisited_nodes = set(graph.nodes)
# create a dictionary to hold the shortest path to each node
shortest_paths = {node: float('inf') for node in graph.nodes}
# set the distance from the start node to itself to 0
shortest_paths[start] = 0
# while there are nodes to evaluate
while unvisited_nodes:
# find the unvisited node with the smallest distance
current_node, current_distance = sorted(
[(node, shortest_paths[node]) for node in unvisited_nodes],
key=lambda x: x[1])[0]
# remove the current node from the unvisited nodes
unvisited_nodes.remove(current_node)
# for each neighbour of the current node
for neighbour, distance in graph.edges[current_node].items():
# if the distance to the neighbour is lower than the current
# distance
if distance + current_distance < shortest_paths[neighbour]:
# update the distance to the neighbour
shortest_paths[neighbour] = distance + current_distance
return shortest_paths``````

## Conclusion

You could use these codes explaining dijkstra algorithm.