bfs dfs dijkstra's bellman-ford's num islands max island docs

Dijkstra's shortest path algorithm visualization

Speed

Obstacles

 

Controls

Speed - increase or decrease the speed of the visualization

Obstacles- - create walls/obstacles, on a map these can be buildings or structures which hinder a path. You can adjust the number of obstacles generated per click.
- You can also click on the grid cells to create obstacles.

Start - After adjusting the speed and creating obstacles, you can now start the visualization to see the workings of the algorithm.

Manual - After running the visualization normally you can run it manually to see how the shortest path was obtained. After the click you can proceed with pressing enter key.

Clear Path - After visualizing, you may opt to clear the path and add more obstacles.

Speed - If the grid becomes to cluttered you can reload it and repeat the above steps.

4
 
This is a node with an assigned weight, which means that from source to a point it will take 4(km/m/cm/hops...) to get to that point.
A
 
Start Node -> this is the starting point(source), search for a path starts here.
B
 
End Node -> where the search stops when a path to destination has been found
 
These act as obstacles, walls. On a real map these may be buildings or structures that may block a shorter path to a destination.
7
 
After the algorithm is complete, we have arrived at the destination, now the shortest path is highlighted in green with the cost of path written in black inside the path.

Dijkstra's shortest path algorithm

This algorithm finds a shortest path tree from a single source node by building a set of nodes that have a minimum distance from the source node.
This algorithm uses a greedy approach in that we find the next best solution in hope that it will lead to a generalized optimal solution. Vertices are denoted by u and v. In our case in the above grid we place the weights inside the vertex denoting the weight to get to it.
Weighted edges that connect two nodes (u, v) are denoted as w(u, v).
dist is an array of distances from source s to every node in the graph. s is initialized as 0 and for all other nodes we initialize them as ∞. dist(v) = ∞
We use a queue (Q) data structure to store all nodes in the graph and at the end of the algorithm the queue will be empty.
S - an empty set to indicate which nodes the algorithm has visited. At the end of the algorithm, S will contain all nodes of the graph.

Algorithm

1. While Q is not empty, we pop the node v that is not in S from Q with the smallest distance dist(v). In the first iteration the source node is chosen because we initialized it with 0. In the following iterations nodes with the smallest weight values will be chosen.

2. We add node v to S, to indicate that v has been visited.

3. We update dist values of adjacent nodes of the current node v by doing the following: for each new adjacent node u,

1. if dist(v) + weight(u,v) < dist(u), that means there is a minimal distance found for u.

1. update dist(u) to the new minimal distance value.

2. Otherwise don't update dist(u).

4. In the end the algorithm has visited all nodes in the graph and dist array will contain the shortest path(smallest distance) from source s to destination.

Computational complexity

This algorithm takes O(V + E log V) in the all cases where V is the number of vertices and E is the number of edges.
It has a O(V) space complexity. It stores V, the number of vertices.

Applications

  • Open Shortest Path First (OSPF) algorithm for packet routing.
  • telephone networking.
  • social network algorithms.
  • maps and gps navigation software.
  • Drone/robotic path routing.
  • Designating a file server.
reference