Dijkstra Algorithm using R
Yogesh Gupta
2023-05-17
Dijkstra Algorithm
Dijkstra’s algorithm has various real-time applications in different domains:
GPS navigation systems: Dijkstra’s algorithm is commonly used in GPS navigation systems to find the shortest path between a source and a destination, allowing users to find optimal routes for driving, walking, or public transportation.
Airline or transportation route planning: Dijkstra’s algorithm can be applied to determine the shortest paths and distances between airports or cities, helping airlines or transportation companies optimize their routes and schedules.
Supply chain management: Dijkstra’s algorithm can assist in optimizing the delivery routes in supply chain management, ensuring that goods are transported efficiently from suppliers to customers.
Loading data
Lets try to find out the shortest path between vertice V1 to Vertice V10 using the algorithm.
library("igraph")##
## Attaching package: 'igraph'## The following objects are masked from 'package:stats':
##
## decompose, spectrum## The following object is masked from 'package:base':
##
## unionM <- as.matrix(read.csv("mst.csv"))
M## V1 V2 V3 V4 V5 V6 V7 V8 V9 V10
## [1,] 0 3 0 0 0 2 0 0 0 0
## [2,] 3 0 17 16 0 0 0 0 0 0
## [3,] 0 17 0 8 0 0 0 0 18 0
## [4,] 0 16 8 0 11 0 0 0 4 0
## [5,] 0 0 0 11 0 1 6 5 10 0
## [6,] 2 0 0 0 1 0 7 0 0 0
## [7,] 0 0 0 0 6 7 0 15 0 0
## [8,] 0 0 0 0 5 0 15 0 12 13
## [9,] 0 0 18 4 10 0 0 12 0 9
## [10,] 0 0 0 0 0 0 0 13 9 0Creating graph with given vertices
The code creates a graph object G using the adjacency matrix M, sets the color of vertices and edges to 2, and plots the graph with edge weights as labels.
G <- graph_from_adjacency_matrix(M, mode='undirected', weighted = TRUE)
V(G)$color = 2
E(G)$color = 2
plot(G, edge.label=E(G)$weight)
Path Calculation
The code calculates the shortest paths from a specific vertex (vertex
1 in this case) to all other vertices in the graph G using
Dijkstra’s algorithm. The shortest.paths() function is used
for this calculation, specifying the graph, the source vertex
(v=1), the target vertices (to=V(G) to include
all vertices), and the algorithm to use
(algorithm="dijkstra").
shortest.paths(G, v=1, to=V(G), algorithm="dijkstra")## V1 V2 V3 V4 V5 V6 V7 V8 V9 V10
## V1 0 3 20 14 3 2 9 8 13 21The code calculates the shortest paths between all pairs of vertices
in the graph G using Dijkstra’s algorithm. The
shortest.paths() function is used with the graph
G, specifying the source vertices (v=V(G) to
include all vertices) and the target vertices (to=V(G) to
include all vertices), and the algorithm to use
(algorithm="dijkstra").
shortest.paths(G, v=V(G), to=V(G), algorithm="dijkstra")## V1 V2 V3 V4 V5 V6 V7 V8 V9 V10
## V1 0 3 20 14 3 2 9 8 13 21
## V2 3 0 17 16 6 5 12 11 16 24
## V3 20 17 0 8 19 20 25 24 12 21
## V4 14 16 8 0 11 12 17 16 4 13
## V5 3 6 19 11 0 1 6 5 10 18
## V6 2 5 20 12 1 0 7 6 11 19
## V7 9 12 25 17 6 7 0 11 16 24
## V8 8 11 24 16 5 6 11 0 12 13
## V9 13 16 12 4 10 11 16 12 0 9
## V10 21 24 21 13 18 19 24 13 9 0Shortest path computation
The code computes the shortest paths and distances from vertex 1 to
all other vertices in the graph G. The
shortest_paths() function is used, specifying the graph
G, the source vertex (1), the target vertices
(to=V(G) to include all vertices), and the
output parameter set to "both" to obtain both
the paths and distances.
shortest_paths(G, 1, to=V(G), output = "both")## $vpath
## $vpath[[1]]
## + 1/10 vertex, named, from 1cec7c8:
## [1] V1
##
## $vpath[[2]]
## + 2/10 vertices, named, from 1cec7c8:
## [1] V1 V2
##
## $vpath[[3]]
## + 3/10 vertices, named, from 1cec7c8:
## [1] V1 V2 V3
##
## $vpath[[4]]
## + 4/10 vertices, named, from 1cec7c8:
## [1] V1 V6 V5 V4
##
## $vpath[[5]]
## + 3/10 vertices, named, from 1cec7c8:
## [1] V1 V6 V5
##
## $vpath[[6]]
## + 2/10 vertices, named, from 1cec7c8:
## [1] V1 V6
##
## $vpath[[7]]
## + 3/10 vertices, named, from 1cec7c8:
## [1] V1 V6 V7
##
## $vpath[[8]]
## + 4/10 vertices, named, from 1cec7c8:
## [1] V1 V6 V5 V8
##
## $vpath[[9]]
## + 4/10 vertices, named, from 1cec7c8:
## [1] V1 V6 V5 V9
##
## $vpath[[10]]
## + 5/10 vertices, named, from 1cec7c8:
## [1] V1 V6 V5 V8 V10
##
##
## $epath
## $epath[[1]]
## + 0/17 edges from 1cec7c8 (vertex names):
##
## $epath[[2]]
## + 1/17 edge from 1cec7c8 (vertex names):
## [1] V1--V2
##
## $epath[[3]]
## + 2/17 edges from 1cec7c8 (vertex names):
## [1] V1--V2 V2--V3
##
## $epath[[4]]
## + 3/17 edges from 1cec7c8 (vertex names):
## [1] V1--V6 V5--V6 V4--V5
##
## $epath[[5]]
## + 2/17 edges from 1cec7c8 (vertex names):
## [1] V1--V6 V5--V6
##
## $epath[[6]]
## + 1/17 edge from 1cec7c8 (vertex names):
## [1] V1--V6
##
## $epath[[7]]
## + 2/17 edges from 1cec7c8 (vertex names):
## [1] V1--V6 V6--V7
##
## $epath[[8]]
## + 3/17 edges from 1cec7c8 (vertex names):
## [1] V1--V6 V5--V6 V5--V8
##
## $epath[[9]]
## + 3/17 edges from 1cec7c8 (vertex names):
## [1] V1--V6 V5--V6 V5--V9
##
## $epath[[10]]
## + 4/17 edges from 1cec7c8 (vertex names):
## [1] V1--V6 V5--V6 V5--V8 V8--V10
##
##
## $predecessors
## NULL
##
## $inbound_edges
## NULLFinal shortest path
sciezka <- shortest_paths(G, 1, to=V(G))$vpath[[10]]
V(G)[sciezka]$color <- 6
sciezka2 <- shortest_paths(G, 1, to=V(G), output = "both")$epath[[10]]
E(G)[sciezka2]$color <- 6
plot(G,edge.label=E(G)$weight)
The code assigns the variable sciezka to store the
shortest path from vertex 1 to vertex 10 in the graph G.
Then, it sets the color attribute of the vertices in the path to 6 using
V(G)[sciezka]$color <- 6.
Next, it assigns the variable sciezka2 to store the edge
sequence of the shortest path from vertex 1 to vertex 10. It sets the
color attribute of the edges in the path to 6 using
E(G)[sciezka2]$color <- 6.
Finally, it plots the graph G with edge labels
representing the weights.
This code visualizes the graph with the shortest path from vertex 1 to vertex 10 highlighted in color 6 for both the vertices and edges.