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
visited.add(current)
# 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
visited.add(current)
# 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 distance3. 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
visited.add(current_node)
# 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_pathsConclusion
You could use these codes explaining dijkstra algorithm.