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

Bellman ford's single source 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.

Bellman Ford Algorithm.

This is a single source shortest path algorithm that finds the shortest path in a graph containing negative edge weights but no negative cycles. It is slower than dijkstra's algorithm but it is more versatile as it is capable of handling negative weights. It is based on the principle of relaxation, whereby the shortest distance for all vertices is gradually replaced by more accurate values until eventually reaching the optimum solution.

Algorithm

1. Initialize distances from source to all vertices as infinity ans set source distance to 0. Create an array distance[] of size |V| with all values as infinite except distance[source].

2. Calculate shortest distances by doing the following |V| - 1 times where |V| is the number of vertices.(In this visualization we dont perform relaxation 800 times as it is time consuming considering some vertices wont change after n number of relaxations).

1. For each edge (u,v) if distance[v] > distance[u] + weight of edge (u,v), update distance[v]. (distance[v] = distance[u] + weight(u, v)).

3. If distance[v] > distance[u] + weight(u,v) then graph contains a negative weight cycle therefore terminate the algorithm and return.

Step 2 guarantees the shortest distances if the graph does not contain negative cycles, which means if the next iteration produces a shorter path for any vertex then there exists a negative weight cycle.

Computational complexity

The algorithm has O(VE) time complexity in the average and best cases and O(E) time complexity in the best case. The space complexity is O(V) as we store vertices in memory.

Applications

  • Detecting negative cycles.
  • Network packet routing protocols
  • telephone networking.
  • Distributed systems.
  • maps and gps navigation software.
  • Drone/robotic path routing.

References

bellman ford algorithm