Loading lesson path
Concept visual
Start from A
Dijkstra's shortest path algorithm was invented in 1956 by the Dutch computer scientist Edsger W. Dijkstra during a twenty minutes coffee break, while out shopping with his fiancée in Amsterdam. The reason for inventing the algorithm was to test a new computer called ARMAC.
Dijkstra's algorithm finds the shortest path from one vertex to all other vertices. It does so by repeatedly selecting the nearest unvisited vertex and calculating the distance to all the unvisited neighboring vertices.
Dijkstra's algorithm is often considered to be the most straightforward algorithm for solving the shortest path problem. Dijkstra's algorithm is used for solving single-source shortest path problems for directed or undirected paths. Single-source means that one vertex is chosen to be the start, and the algorithm will find the shortest path from that vertex to all other vertices. Dijkstra's algorithm does not work for graphs with negative edges. For graphs with negative edges, the Bellman-Ford algorithm that is described on the next page, can be used instead. To find the shortest path, Dijkstra's algorithm needs to know which vertex is the source, it needs a way to mark vertices as visited, and it needs an overview of the current shortest distance to each vertex as it works its way through the graph, updating these distances when a shorter distance is found.
Set initial distances for all vertices: 0 for the source vertex, and infinity for all the other. Choose the unvisited vertex with the shortest distance from the start to be the current vertex. So the algorithm will always start with the source as the current vertex. For each of the current vertex's unvisited neighbor vertices, calculate the distance from the source and update the distance if the new, calculated, distance is lower. We are now done with the current vertex, so we mark it as visited. A visited vertex is not checked again. Go back to step 2 to choose a new current vertex, and keep repeating these steps until all vertices are visited. In the end we are left with the shortest path from the source vertex to every other vertex in the graph. In the animation above, when a vertex is marked as visited, the vertex and its edges become faded to indicate that Dijkstra's algorithm is now done with that vertex, and will not visit it again.
This basic version of Dijkstra's algorithm gives us the value of the shortest path cost to every vertex, but not what the actual path is. So for example, in the animation above, we get the shortest path cost value 10 to vertex F, but the algorithm does not give us which vertices (D->E->C->D->F) that make up this shortest path. We will add this functionality further down here on this page.
Run the simulation below to get a more detailed understanding of how Dijkstra's algorithm runs on a specific graph, finding the shortest distances from vertex D. inf F
inf B inf C
inf A
inf E
D inf G
This simulation shows how distances are calculated from vertex D to all other vertices, by always choosing the next vertex to be the closest unvisited vertex from the starting point. Follow the step-by-step description below to get all the details of how Dijkstra's algorithm calculates the shortest distances.
Consider the Graph below. F
B C
A
E D G We want to find the shortest path from the source vertex D to all other vertices, so that for example the shortest path to C is D->E->C, with path weight 2+4=6. To find the shortest path, Dijkstra's algorithm uses an array with the distances to all other vertices, and initially sets these distances to infinite, or a very big number. And the distance to the vertex we start from (the source) is set to 0. distances = [inf, inf, inf, 0, inf, inf, inf] #vertices [ A , B , C , D, E , F , G ] The image below shows the initial infinite distances to other vertices from the starting vertex D. The distance value for vertex D is 0 because that is the starting point. inf F
inf B inf C
inf A
inf E
D inf G Dijkstra's algorithm then sets vertex D as the current vertex, and looks at the distance to the adjacent vertices. Since the initial distance to vertices A and E is infinite, the new distance to these are updated with the edge weights. So vertex A gets the distance changed from inf to 4, and vertex E gets the distance changed to 2. As mentioned on the previous page, updating the distance values in this way is called 'relaxing'. inf F
inf B inf C
A
E
D inf G After relaxing vertices A and E, vertex D is considered visited, and will not be visited again. The next vertex to be chosen as the current vertex must the vertex with the shortest distance to the source vertex (vertex D), among the previously unvisited vertices. Vertex E is therefore chosen as the current vertex after vertex D. inf F
inf B
C
A
E
D
G The distance to all adjacent and not previously visited vertices from vertex E must now be calculated, and updated if needed. The calculated distance from D to vertex A, via E, is 2+4=6. But the current distance to vertex A is already 4, which is lower, so the distance to vertex A is not updated.
Formula
The distance to vertex C is calculated to be 2 + 4 = 6, which is less than infinity, so the distance to vertex C is updated.
Similarly, the distance to node G is calculated and updated to be 2 + 5 = 7.The next vertex to be visited is vertex A because it has the shortest distance from D of all the unvisited vertices. inf F
inf B
C
A
E
D
G The calculated distance to vertex C, via A, is 4+3=7, which is higher than the already set distance to vertex C, so the distance to vertex C is not updated. Vertex A is now marked as visited, and the next current vertex is vertex C because that has the lowest distance from vertex D between the remaining unvisited vertices. 11 F
B
C
A
E
D
G
Formula
Vertex F gets updated distance 6 + 5 = 11, and vertex B gets updated distance 6 + 2 = 8.Calculated distance to vertex G via vertex C is 6+5=11 which is higher than the already set distance of 7, so distance to vertex G is not updated. Vertex C is marked as visited, and the next vertex to be visited is G because is has the lowest distance between the remaining unvisited vertices. 11 F
B
C
A
E
D
G Vertex F already has a distance of 11. This is lower than the calculated distance from G, which is 7+5=12, so the distance to vertex F is not updated. Vertex G is marked as visited, and B becomes the current vertex because it has the lowest distance of the remaining unvisited vertices. 10 F
B
C
A
E
D
G
Formula
The new distance to F via B is 8 + 2 = 10, because it is lower than F's existing distance of 11.Vertex B is marked as visited, and there is nothing to check for the last unvisited vertex F, so Dijkstra's algorithm is finished. Every vertex has been visited only once, and the result is the lowest distance from the source vertex D to every other vertex in the graph.
To implement Dijkstra's algorithm, we create a Graph class. The Graph represents the graph with its vertices and edges: class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]Formula
self.size = size self.vertex_data = [''] * sizedef add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight self.adj_matrix[v][u] = weight # For undirected graphdef add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = dataWe create the adj_matrix to hold all the edges and edge weights. Initial values are set to .
size is the number of vertices in the graph.
The vertex_data holds the names of all the vertices.
The add_edge method is used to add an edge from vertex u to vertex v, with edge weight weight.
The add_vertex_data method is used to add a vertex to the graph. The index where the vertex should belong is given with the vertex argument, and data is the name of the vertex.
Graph class also contains the method that runs Dijkstra's algorithm:
def dijkstra(self, start_vertex_data):Formula
start_vertex = self.vertex_data.index(start_vertex_data)distances = [float('inf')] * self.size distances[start_vertex] = 0 visited = [False] * self.size
for _ in range(self.size):
Formula
min_distance = float('inf')
u = None for i in range(self.size):
if not visited[i] and distances[i] < min_distance:
min_distance = distances[i]
u = iif u is None: break
visited[u] = True
for v in range(self.size): if self.adj_matrix[u][v] != 0 and not visited[v]:
Formula
alt = distances[u] + self.adj_matrix[u][v]
if alt < distances[v]:distances[v] = alt
return distancesThe initial distance is set to infinity for all vertices in the distances array, except for the start vertex, where the distance is 0.
False to mark them as not visited in the visited array.
The next current vertex is found. Outgoing edges from this vertex will be checked to see if shorter distances can be found. It is the unvisited vertex with the lowest distance from the start.
If the next current vertex has not been found, the algorithm is finished. This means that all vertices that are reachable from the source have been visited.
The current vertex is set as visited before relaxing adjacent vertices. This is more effective because we avoid checking the distance to the current vertex itself.
Distances are calculated for not visited adjacent vertices, and updated if the new calculated distance is lower.
Graph class, the vertices and edges must be defined to initialize the specific graph, and the complete code for this Dijkstra's algorithm example looks like this: