Mini Project on Bellman-Ford algorithm using OpenGL

Descriptions : The Bellman-Ford algorithm also known as Ford-Fulkerson algorithm is based on the principle that is intuitively easy to understand. Each node A knows the shortest path to node Z, then node A can determine its shortest path to Z by calculating the minimum cost.

Each node connected to another node with a cost, now when the packet flows through a path it result some cost to the network . To minimize the cost of network communication Bellman-Ford algorithm is implemented and the packet flow to the path which costs less in the communication. 

Working Principle

       

               First  we draw the nodes and connecting lines by passing co-ordinate values to a GL_LINES .It will draw the network and connections of the network. The shortest path is calculated by using Bellman-Ford algorithm using the following formula-

1.Initialization

                                             Di=∞; for all i≠ d                                 (3.1)

                                             Dd=0                                                     (3.2)

            2.Updation

                                             Di=minj{Cij+Dj}                                              (3.3)

Repeat step 2 until no more change occur in iteration.

To draw the packet we pass the co-ordinate values to the GL_QUAD. Now to move the packet from one node to another node we draw the packet at different points of co-ordinate using for loop. The loop will make the polygon in the certain color specified from the starting co-ordinate to the end with the incremented value. Now we cover the part of the long polygon which is generated in the loop using the same co-ordinate values and loop coloring with black. The black color cover the previous color and this makes the sense for the movement of the packet. Similar thing is done for all the packet movement

Usages : 

Mouse interaction : Click on the node to choose the node from where the shortest distance is to be measured. Click on quit block to exit the program.

Key board : The program will ask after every node select, showing the shortest path if you wan to continue or not press y to continue press n to exit the program.

Download : Project Code