Question # 1

What are the differences between Bellman Ford’s and

Dijkstra’s algorithms?
Bellman Ford’s algorithm:
Like other Dynamic Programming Problems, the algorithm calculates shortest paths in a bottom-
up manner. It first calculates the shortest distances which have at-most one edge in the path.
Then, it calculates the shortest paths with at-most 2 edges, and so on. After the i-th iteration of
outer loop, the shortest paths with at most i edges are calculated. There can be maximum |V| – 1
edge in any simple path that is why the outer loop runs |v| – 1 time. The idea is, assuming that
there is no negative weight cycle if we have calculated shortest paths with at most i edges, then
an iteration over all edges guarantees to give the shortest path with at-most (i+1) edges

Dijkstra’s algorithm:
Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s
MST, we generate an SPT (shortest path tree) with a given source as root. We maintain two sets,
one set contains vertices included in the shortest-path tree, other set includes vertices not yet
included in the shortest-path tree. At every step of the algorithm, we find a vertex which is in the
other set (set of not yet included) and has a minimum distance from the source.
Differences between Bellman Ford’s and Dijkstra’s algorithm:
Bellman Ford’s algorithm and Dijkstra’s algorithm both are single-source shortest path
algorithm, i.e. both determines the shortest distance of each vertex of a graph from a single
source vertex. However, there are some key differences between them. We follow the Dynamic
Programming approach in Bellman Ford’s algorithm and Greedy approach in Dijkstra’s
algorithm.

Let’s see the other major differences between these two techniques-

BELLMAN FORD’S ALGORITHM DIJKSTRA’S ALGORITHM

Bellman Ford’s Algorithm works when

there is negative weight edge, it also Dijkstra’s Algorithm doesn’t work when there

detects the negative weight cycle. is negative weight edge.

 BELLMAN FORD’S ALGORITHM DIJKSTRA’S ALGORITHM

The result contains the vertices which The result contains the vertices containing

contains the information about the other whole information about the network, not

vertices they are connected to. only the vertices they are connected to.

It can easily be implemented in a It cannot be implemented easily in a

distributed way. distributed way.

It is more time consuming than Bellman

It is relatively less time consuming. Ford’s algorithm.

Dynamic Programming approach is taken Greedy approach is taken to implement the

to implement the algorithm. algorithm.

Question # 2
Example of Dijkstra’s Algorithm and Prim’s Algorithm?
Distra’s Algorithm:

Dijkstra's Algorithm allows you to calculate the shortest path between one node (you pick which
one) and every other node in the graph. You'll find a description of the algorithm at the end of
this page, but, let's study the algorithm with an explained example! Let's calculate the shortest
path between node C and the other nodes in our graph:

During the algorithm execution, we'll mark every node with its minimum distance to node C (our
selected node). For node C, this distance is 0. For the rest of nodes, as we still don't know that
minimum distance, it starts being infinity (∞):

We'll also have a current node. Initially, we set it to C (our selected node). In the image, we mark
the current node with a red dot.

Now, we check the neighbours of our current node (A, B and D) in no specific order. Let's begin
with B. We add the minimum distance of the current node (in this case, 0) with the weight of the
edge that connects our current node with B (in this case, 7), and we obtain 0 + 7 = 7. We
compare that value with the minimum distance of B (infinity); the lowest value is the one that
remains as the minimum distance of B (in this case, 7 is less than infinity):
So far, so good. Now, let's check neighbour A. We add 0 (the minimum distance of C, our
current node) with 1 (the weight of the edge connecting our current node with A) to obtain 1. We
compare that 1 with the minimum distance of A (infinity), and leave the smallest value:

OK. Repeat the same procedure for D:

Great. We have checked all the neighbours of C. Because of that, we mark it as visited. Let's
represent visited nodes with a green check mark:

We now need to pick a new current node. That node must be the unvisited node with the smallest
minimum distance (so, the node with the smallest number and no check mark). That's A. Let's
mark it with the red dot:

And now we repeat the algorithm. We check the neighbours of our current node, ignoring the
visited nodes. This means we only check B.

For B, we add 1 (the minimum distance of A, our current node) with 3 (the weight of the edge
connecting A and B) to obtain 4. We compare that 4 with the minimum distance of B (7) and
leave the smallest value: 4.
Afterwards, we mark A as visited and pick a new current node: D, which is the non-visited node
with the smallest current distance.

We repeat the algorithm again. This time, we check B and E.

For B, we obtain 2 + 5 = 7. We compare that value with B's minimum distance (4) and leave the
smallest value (4). For E, we obtain 2 + 7 = 9, compare it with the minimum distance of E
(infinity) and leave the smallest one (9).

We mark D as visited and set

our current node to B.
Almost there. We only need to check E. 4 + 1 = 5, which is less than E's minimum distance (9),
so we leave the 5. Then, we mark B as visited and set E as the current node.

E doesn't have any non-visited neighbours, so we don't need to check anything. We mark it as
visited.
 As there are not univisited nodes, we're done! The minimum distance of each node now actually
represents the minimum distance from that node to node C (the node we picked as our initial
node)!

Here's a description of the algorithm:

1. Mark your selected initial node with a current distance of 0 and the rest with infinity.
2. Set the non-visited node with the smallest current distance as the current node C.
3. For each neighbour N of your current node C: add the current distance of C with the
weight of the edge connecting C-N. If it's smaller than the current distance of N, set it as the new
current distance of N.
4. Mark the current node C as visited.
5. If there are non-visited nodes, go to step 2.

Prim’s Algorithm and its Example:

Prim’s Algorithm:
 
 Prim’s Algorithm is a famous greedy algorithm.
 It is used for finding the Minimum Spanning Tree (MST) of a given graph.
 To apply Prim’s algorithm, the given graph must be weighted, connected and undirected.
  

Prim’s Algorithm Implementation-

 
The implementation of Prim’s Algorithm is explained in the following steps-

Step-01:
 Randomly choose any vertex.
 The vertex connecting to the edge having least weight is usually selected.
 

Step-02: 
 Find all the edges that connect the tree to new vertices.
 Find the least weight edge among those edges and include it in the existing tree.
 If including that edge creates a cycle, then reject that edge and look for the next least
weight edge.
 

Step-03:
 Keep repeating step-02 until all the vertices are included and Minimum Spanning Tree
(MST) is obtained.
 

Example:
Construct the minimum spanning tree (MST) for the given graph using Prim’s Algorithm-

Start with a weighted graph

Choose a vertex

Choose the shortest edge from this vertex and add it

Choose the nearest vertex not yet in the solution
Choose the nearest edge not yet in the solution, if there are multiple choices, choose one at
random

Repeat until you have a spanning tree