Question

Using the provided network diagram, write a program in c ++ that finds the shortest path routing using the Bellman-Ford algorithm. Your program should represent the fact that your node is U. Show how the iterative process generates the routing table for your node. One of the keys to your program will be in determining when the iterative process is done.

Deliverables 1. Provide an output that shows the routing table for your node after each iteration. Add a second table with two columns. One that shows the destination from your node and the second column indicating the number of hops to reach that node. 2. Provide a Word document that explains how your program incorporates the Bellman-Ford algorithm. Ensure you explain how you incorporated the iterative process and determined when the routing table for your node was optimum. You can incorporate your outputs into this document; however, you must identify where in your source code you print the results. 3. Provide a copy of your source code

Answer 1

Here is Implemetation of Bellman-Ford algorithm in C++ language.

Please Upvote or hit that like,thumbs-up button.

Bellman_Ford_algo.cpp

#include<iostream>
// Defining MAX size to 10
#define MAX 10

using namespace std;

typedef struct Edge
{
  int source;
  int destination;
  int weight;
}Edge;

void bellman_ford_algo(int nodevertex,Edge edge[],int source_graph,int nodeedge)
{
  int u,v,weight,i,j=0;
  int distance[MAX];

  for(i=0;i<nodevertex;i++)
  {
    distance[i]=999;
  }

  // distance of source vertex
  distance[source_graph]=0;

  // free all the edges nodevertex - 1 times
  for(i=0;i<nodevertex-1;i++)
  {
    for(j=0;j<nodeedge;j++)
    {
      u=edge[j].source;
      v=edge[j].destination;
      weight=edge[j].weight;


      if(distance[u]!=999 && distance[u]+weight < distance[v])
      {
        distance[v]=distance[u]+weight;
      }
    }

  }

  // checking for negative cycle
  for(j=0;j<nodeedge;j++)
  {
    u=edge[j].source;
    v=edge[j].destination;
    weight=edge[j].weight;

    if(distance[u]+weight < distance[v])
    {
      cout<<"\n\nNegative Cycle present..!!\n";
      return;
    }
  }

  cout<<"\nVertex"<<"  Distance from source";
  for(i=1;i<=nodevertex;i++)
  {
    cout<<"\n"<<i<<"\t"<<distance[i];
  }

}


int main()
{
  int nodevertex,nodeedge,source_graph;
  Edge edge[MAX];

  cout<<"Enter the number of vertices you want : ";
  cin>>nodevertex;


  printf("Enter the source vertex of the graph: ");
  cin>>source_graph;

  cout<<"\nEnter no. of edges you want : ";
  cin>>nodeedge;

  for(int i=0;i<nodeedge;i++)
  {
    cout<<"\nEdge Number "<<i+1<<"=";
    cout<<"\nEnter source vertex here :";
    cin>>edge[i].source;
    cout<<"Enter destination vertex here:";
    cin>>edge[i].destination;
    cout<<"Enter weight here :";
    cin>>edge[i].weight;
  }

  bellman_ford_algo(nodevertex,edge,source_graph,nodeedge);

  return 0;
}

Output:- Refer to screenshot

Again, Please hit that like button , it really motivates me<3

Thank you!!

Have a nice day:)