Shortest Path Algorithms Visualizer
Welcome to Shortest Path Algorithms Visualizer. This is a tool to help you visualize how the algorithms, used for solving Shortest Path Problem, work in real time.
So, what is the Shortest Path Problem ?
Shortest Path Problem
The shortest path problem in graph theory, is a Combinatorial Optimization problem. The problem requires one to find a path between a source and a destination, such that travelling through the found path, costs the least. For the sake of problem-solving, this problem is interesting enough to try and solve. However, what makes this, one of the most-studied combinatorial optimization problem is the real life scenarios, that deal with this problem, as their primary application or as a subproblem of their primary application. Below are a few examples of such real life scenarios:
- Finding Shortest Path between two places in applications like GPS-enabled Google Maps, Waze. How does this work ?
- Used in IP routing. IP routing uses Open Shortest Path First (OSPF) routing protocol, that uses a shortest path problem solving algorithm named as Dijkstra's algorithm.
- Communication Networks use shortest path problem solving algorithms to minimize network wide cost and regulate network traffic flows.
Over the time, various algorithms has been conceived to solve the shortest path problem. These algorithms both have their own advantages and disadvantages depending on the applications, they are used in. Here, however, only few of them has been implemented for visualization.
These are:
- BFS(Breadth First Search)
- Dijkstra's Algorithm
- Bellman Ford Algorithm
- Floyd Warshall Algorithm
It is strongly recommended to go through the algorithms first, then proceed to visualization.
Breadth First Search is a Single-Source-Shortest-Path (SSSP) graph traversal algorithm for unweighted graph, in which we visit the source vertex first and mark it as visited. Then we visit all adjacent, not-visited vertices of the source vertex, mark them visited and then we visit adjacent, not-visited vertices of these vertices and so on..
Also, BFS with simple modification (0-1 BFS) can give shortest path from source to destination for binary weighted graph.
- Idea behind the algorithm
Since during breadth first search, total encounterd distance keeps increasing by 1, i.e. we first travel source vertex (at distance 0), then travel vertices, those are at distance 1 from source, then vertices at distance 2 from source and so on, hence, the first time we encounter a vertex, the distance covered till now, must be the shortest distance.
function BFS(Graph[V], source, destination) {
1. initialize distance[V] = {INF, INF, INF, INF,.......}
2. distance[source] = 0
3. create an empty Queue (say 'q')
4. add source vertex to q
5. while (q is not empty)
vertex u := q.dequeue() {
for (all vertices v: adjacent of u) {
if (distance[v] == INF) { // if vertex is not visited
distance[v] = distance[u] + 1
q.enqueue(v)
}
}
}
6. return distance[destination]
}
- Time Complexity:
- O(V+E), where V = number of vertices and E = number of edges
- Pros
- Gives shortest path for unweighted graph
- Works for both directed & undirected graph
- Easy to implement
- Cons
- Does not work for weighted graph
Dijkstra's Shortest-Path-First (SPF) algorithm is a greedy single-source-shortest-path algorithm, conceived by Edsger. W Dijkstra in 1956.
- Idea behind the algorithm
- We maintain a container of distance for all vertices initialized with values Infinite.
- Distance of source vertex is 0.
- At each iteration, we pick a vertex and finalize it distance. Initially none of the vertices have their distance finalized.
- How do we pick the vertex ?
- We pick the vertex for which distance has not been finalized and has minimum distance. (greedy choice)
- Then we go to all adjacent vertices of it, and check whether do we get a shorter path to those vertices, through current vertex, If yes, then we update it's distance.
function Dijkstra(Graph[V], source, destination) {
1. create a Priority Queue (Min Heap), say 'pq'
2. intialize distance[V] = {INF, INF, INF, INF, INF,........}
3. distance[source] = 0
4. insert all vertices with distance[vertex] to pq // O(V) time
5. while (pq is not empty) { // loop runs V times
vertex u := extract vertex with minimum distance from pq // O(log V) time, overall time: O(V log V)
if (u == destination) {
return distance[destination]
}
for (all vertices v: adjacent of u) {
if (distance[v] > distance[u] + weight(u, v)) {
distance[v] = distance[u] + weight(u, v)
insert vertex v with distance[v] to pq // overall time: O(E log V)
}
}
}
}
- Time Complexity:
- O(Vlog V + Elog V), where V = number of vertices and E = number of edges
- Pros
- Works for both weighted & unweighted graph
- Works for both cyclic & acyclic graph
- Works for both directed & undirected graph
- Cons
- Does not work for graph with negative weighted edges
Bellman Ford shortest path algorithm is a dynamic programming based algorithm that computes from source node all reachable nodes. This algorithm was proposed by Alfonso Shimbel and was named after it's publishers Richard Bellman and Lester Ford Jr. .Even though this algorithm is relatively slower than Dijkstra's algorithm, it has one major advantage that, it can detect negative weighted edge cycles.
- Idea behind the algorithm
- The key idea of the algorithm is If there are V vertices in a graph (that does not contain negative weighted edge cycles), then any existing shortest path, between any source and destination vertex can not have length more than V-1.
- We first find out the shortest path containing 1 edge, then shortest path containing 2 edges, then 3 edges and so on..
function BellmanFord(Graph[V], source, destination) {
1. intialize distance[V] = {INF, INF, INF, INF, INF,........}
2. distance[source] = 0
3. for (count 0 to V-1) {
for (every edge u to v) {
if (distance[v] > distance[u] + weight(u, v)) {
distance[v] = distance[u] + weight(u, v)
}
}
}
/*
For detection of negative weighted edge cycles,
we run one more loop to check whether finalized
distances are further reducing or not. If yes,
then report negative weighted edge cycle
*/
4. for (every edge u to v) {
if (distance[v] > distance[u] + weight(u, v)) {
report (negative weighted edge cycle exists)
return
}
}
5. return distance[detination]
}
- Time Complexity:
- O(VE), where V = number of vertices and E = number of edges
- Pros
- Works for both weighted & unweighted graph
- Works for both cyclic & acyclic graph
- Works for both directed & undirected graph
- Works for negative weight edges
- Detects negative weight edge cycles, if any
- Cons
- slower than Dijkstra's algorithm
Floyd Warshall All-Pair-Shortest-Path (APSP) algorithm is a dynamic programming based algorithm, that computes shortest distances between all possible pair(source, destination) of vertices. This algorithm is relatively slower than even Bellman Ford algorithm. For even slightly higher number of vertices this algorithm takes quite some time to compute all pair shortest paths.
The crucial advantage of this algorithm is that, after computation, it gives shortest paths among all possible pairs of source and destination vertex, iff path exists.
- Idea behind the algorithm
- For each vertex, we update all shortest path from any source to any destination vertex, that contains this vertex as an intermediate vertx.
- For all pairs of source to destination, we check whether through this intermediate vertex, a shorter path is possible or not.
function FloydWarshall(Graph[V], source, destination) {
1. intialize distance[V][V]
2. for (i from 1 to V) {
for (j from 1 to V) {
if (edge from i to j exists) {
distance[i][j] = weight(i, j)
}
else if (i == j) {
distance[i][j] = 0
}
else {
distance[i][j] = INF
}
}
}
3. for (k from 1 to V) {
for (i from 1 to V) {
for (j from 1 to V) {
if (distance[i][k] === INF || distance[k][j] === INF) {
continue
}
if (distance[i][j] > distance[i][k] + distance[k][j]) {
distance[i][j] = distance[i][k] + distance[k][j]
}
}
}
}
4. return distance[source][destination]
}
- Time Complexity:
- O(V³), where V = number of vertices
- Pros
- Works for both weighted & unweighted graph
- Works for both cyclic & acyclic graph
- Works for both directed & undirected graph
- Works for negative weight edges
- Detects negative weight edge cycles, if any
- Cons
- Time Complexity very high
Select an algorithm from dropdown
Visualize the algorithm
Clear Path or Reconfigure the Grid
Continue from the beginning
Source Node
Destination Node
Node present in the shortest path from source to destination
Node, for which shortest distance has been finalized
Node, which has been visited atleast once
(only for Floyd Warshall Algorithm visualization) Current Intermediate Node, that is being processed
(only for Floyd Warshall Algorithm visualization) Node, which has been visited atleast once
For Bellman Ford algorithm visualization, in worst case, it takes around 2.5 minutes to visualize the complete animation (despite all my efforts to optimize it without losing significant visualization details). Even though on average it takes around 1.5 minutes to complete the animations.
For Floyd Warshall Algorithm visualization, I have disabled the animations for current source Node and current destination Node, that are being processed. Animations are enabled only for current intermediate Node. The reason being:
- For the 10 × 10 grid, there are 100 possible vertices. The algorithm has cubic time complexity.
- For 100 vertices: 10,00,000 units of animation lapse duration takes a lot of time.
- It took around 15 minutes, with all animation enabled with optimal animation lapse timing for proper visualization.