Given a graph(directed or undirected), we want to find the shortest path to all the nodes in a graph from a single source node as starting point for distance calculation.
Graph that we will be using in this post, it is a directed weighted graph:
We represent our graph in adjacency matrix shown below:
graph = [
[0, 2, 4, 0, 0, 0],
[0, 0, 1, 7, 0, 0],
[0, 0, 0, 0, 3, 0],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 2, 0, 5],
[0, 0, 0, 0, 0, 0],
];
More can be read on the adjacency matrix before moving further, have added a link in references.
ALGORITHM:
Let the starting node or our source vertex to be called as the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra's algorithm will initially start with infinite distances and will try to improve them step by step as done in a greedy approach.
1) Mark all nodes as unvisited in TreeSet. Create a set of all the unvisited nodes called the unvisited set.
# initial state of the six vertices, false as all unvisted
TreeSet = [ false, false, false, false, false, false]
2) Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes(this can be seen in the output of program as initially all nodes distance other than starting node is assigned as INF). The tentative distance of a node v is the length of the shortest path discovered so far between the node v and the starting node. Since initially no path is known to any other vertex than the source itself (which is a path of length zero), all other tentative distances are initially set to infinity. Set the initial node as current.
# initially dist is something like below:
dist = [ Inf, Inf, Inf, Inf, Inf, Inf]
# we know distance of starting node 1 from node 1 so
dist = [0.0 , Inf, Inf, Inf, Inf, Inf]
3) For the current node, consider all of its unvisited neighbors and calculate their tentative distances through the current node. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one in the distance array. This is the relaxation mechanism
# for our current node 1, node 2 and node 3 are connected
# with distances being 2 and 4 respectively, others
# stay Inf as those are not connected to current node.
dist = [0.0, 2.0, 4.0, Inf, Inf, Inf] # relaxation procedure
4) When we are done considering all of the unvisited neighbors of the current node, mark the current node as visited(update TreeSet) and remove it from the unvisited set. A visited node will never be checked again.
5) If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished.
6) Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new current node, and go back to step 3.
#consider the distances now
dist = [0.0, 2.0, 4.0, Inf, Inf, Inf]
# so the next unvisted node with smallest tentative distance
# is node 2, so we change the current node to 2 and repeat
# from step3
# for our current node 2, node 3 and node 4 are connected
# with distances being 1 and 7 respectively, others
# stay Inf as those are not connected to current node.
dist = [0.0, 2.0, 4.0, Inf, Inf, Inf] # before relaxation procedure
# After relaxation: [0.0, 2.0, 3.0, 9.0, Inf, Inf]
# Dist for updated from 4.0 to 3.0 as the according to step4,
# we check and update based on min(current_dist(node3), dist(node1-node2) + dist(node2-node3))
# so dist(1-2)+ dist(2-3) = 3.0 which is less than current distance of 4.0
# Dist for 4 -> as dist(node1-node2) + dist(node2-node4)
Code:
# To find the vertex with
# minimum distance value, from the set of vertices
# not yet included in shortest path tree
function mindist(dist, sptset)
min = Inf # Initialize minimum distance for next node
minindex = 0
# Search smallest value nearest vertex not in the
# shortest path tree
for i in 1:size(graph)[1]
if dist[i] < min && sptset[i] == false
min = dist[i]
minindex = i
end
end
println("\nNext Node to be processed: ", minindex)
return minindex
end
# Dijkstra's single source
# shortest path algorithm for a graph represented
# using adjacency matrix representation
function dijkstra(graph, initial_node)
println("Source Node:", initial_node)
println("Graph's Adjacency Matrix:\n", graph)
TreeSet = [false for i in 1:size(graph)[1]] # step 1
dist = [Inf for i in 1:size(graph)[1]] # step 2
dist[initial_node] = 0
for i in 1:size(graph)[1]
# Pick the minimum distance vertex from
# the set of vertices not yet processed.
x = mindist(dist, TreeSet) # step 3
println("Before relaxation: ", dist)
# step 3 -> relaxation procedure
# Update dist value of the adjacent vertices
# of the picked vertex only if the current
# distance is greater than new distance and
# the vertex in not in the shortest path tree
for j in 1:size(graph)[1]
if graph[x][j] > 0 && TreeSet[j] == false && dist[j] > dist[x] + graph[x][j]
dist[j] = dist[x] + graph[x][j]
end
end
println("After relaxation: ", dist)
# Put the minimum distance vertex in the
# shortest path tree
TreeSet[x] = true # step 4
end
println("v | d[v] ")
println("---------")
for (i , j) in enumerate(dist)
println(i, " | ", j)
end
end
graph = [
[0, 2, 4, 0, 0, 0],
[0, 0, 1, 7, 0, 0],
[0, 0, 0, 0, 3, 0],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 2, 0, 5],
[0, 0, 0, 0, 0, 0],
];
dijkstra(graph, 1)
Output:
(base) ashwani@user:~/practice$ julia dijkstra.jl
Source Node:1
Graph's Adjacency Matrix:
[[0, 2, 4, 0, 0, 0],
[0, 0, 1, 7, 0, 0],
[0, 0, 0, 0, 3, 0],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 2, 0, 5],
[0, 0, 0, 0, 0, 0]]
Next Node to be processed: 1
Before relaxation: [0.0, Inf, Inf, Inf, Inf, Inf]
After relaxation: [0.0, 2.0, 4.0, Inf, Inf, Inf]
Next Node to be processed: 2
Before relaxation: [0.0, 2.0, 4.0, Inf, Inf, Inf]
After relaxation: [0.0, 2.0, 3.0, 9.0, Inf, Inf]
Next Node to be processed: 3
Before relaxation: [0.0, 2.0, 3.0, 9.0, Inf, Inf]
After relaxation: [0.0, 2.0, 3.0, 9.0, 6.0, Inf]
Next Node to be processed: 5
Before relaxation: [0.0, 2.0, 3.0, 9.0, 6.0, Inf]
After relaxation: [0.0, 2.0, 3.0, 8.0, 6.0, 11.0]
Next Node to be processed: 4
Before relaxation: [0.0, 2.0, 3.0, 8.0, 6.0, 11.0]
After relaxation: [0.0, 2.0, 3.0, 8.0, 6.0, 9.0]
Next Node to be processed: 6
Before relaxation: [0.0, 2.0, 3.0, 8.0, 6.0, 9.0]
After relaxation: [0.0, 2.0, 3.0, 8.0, 6.0, 9.0]
v | d[v]
---------
1 | 0.0
2 | 2.0
3 | 3.0
4 | 8.0
5 | 6.0
6 | 9.0
Top comments (0)