Tools Inoduction to Alp sign In Home Page ThmbnalsX Export PDF Create Por Edit P

Question

Tools Inoduction to Alp sign In Home Page ThmbnalsX Export PDF Create Por Edit PDF Adobe Acrobat Pro DC Commen Combine Files afa & Sign Send for Signature Figere 244 The esecutiee ed the Belinan Food a ponthm. The iorce is etes s. The d tes appear wihin the ventices, and shaded edges indicate predecessor values if edge (, ) hadod. then v. =M· lntes particular example, each pass nelanes the edges in the ole" Send &Trak; Erst pass oer the elges(bh t The stuaion affer each sucessine pass ouer the edgs. The Lemma 242 Let G -(V. E) be a weighted, directed graph with source s and weight fune tion w : E R, and assume that G contains no negative-weight cycles that are reachable from s. Then, after the IV terations of the for loop of lines 2-4 of BELLMAN-FORD, we have v.d m (s,v) for all vertices v that are reachable from a 615 Store and share es in the

Explanation / Answer

Program:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

// a structure to represent a weighted edge in graph
struct Edge
{
   int src, dest, weight;
};

// a structure to represent a connected, directed and
// weighted graph
struct Graph
{
   // V-> Number of vertices, E-> Number of edges
   int V, E;

   // graph is represented as an array of edges.
   struct Edge* edge;
};

// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
   struct Graph* graph =
       (struct Graph*) malloc( sizeof(struct Graph) );
   graph->V = V;
   graph->E = E;

   graph->edge =
   (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );

   return graph;
}

// A utility function used to print the solution
void printArr(int dist[], int n)
{
   printf("Vertex Distance from Source -------------------------- ");
   for (int i = 0; i < n; ++i)
       printf(" %d %d ", i, dist[i]);
}

// The main function that finds shortest distances from src to
// all other vertices using Bellman-Ford algorithm. The function
// also detects negative weight cycle
void BellmanFord(struct Graph* graph, int src)
   {
   int k=0;
   int V = graph->V;
   int E = graph->E;
   int dist[V];

   // Step 1: Initialize distances from src to all other vertices
   // as INFINITE
   for (int i = 0; i < V; i++)
       dist[i] = INT_MAX;
   dist[src] = 0;

   // Step 2: Relax all edges |V| - 1 times. A simple shortest
   // path from src to any other vertex can have at-most |V| - 1
   // edges
   for (int i = 1; i <= V-1; i++)
   {
       for (int j = 0; j < E; j++)
       {
           int u = graph->edge[j].src;
           int v = graph->edge[j].dest;
           int weight = graph->edge[j].weight;
           if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
               dist[v] = dist[u] + weight;
       }
   printf(" Phase %d: ",k++);
   printArr(dist, V);
   }

   // Step 3: check for negative-weight cycles. The above step
   // guarantees shortest distances if graph doesn't contain
   // negative weight cycle. If we get a shorter path, then there
   // is a cycle.
   for (int i = 0; i < E; i++)
   {
       int u = graph->edge[i].src;
       int v = graph->edge[i].dest;
       int weight = graph->edge[i].weight;
       if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
           printf("Graph contains negative weight cycle");
   }

   return;
}

// Driver program to test above functions
int main()
{
   /* Let us create the graph given in above example */
   int V = 6; // Number of vertices in graph
   int E = 10; // Number of edges in graph
   struct Graph* graph = createGraph(V, E);

   // add edge 0-1 (or A-B in above figure)
   graph->edge[0].src = 0;
   graph->edge[0].dest = 1;
   graph->edge[0].weight = 10;

   // add edge 0-2 (or A-C in above figure)
   graph->edge[1].src = 0;
   graph->edge[1].dest = 2;
   graph->edge[1].weight = 5;

   // add edge 1-2 (or B-C in above figure)
   graph->edge[2].src = 1;
   graph->edge[2].dest = 2;
   graph->edge[2].weight = 2;

   // add edge 1-0 (or B-C in above figure)
   graph->edge[2].src = 1;
   graph->edge[2].dest = 0;
   graph->edge[2].weight = -8;

   // add edge 2-4 (or A-E in above figure)
   graph->edge[4].src = 2;
   graph->edge[4].dest = 4;
   graph->edge[4].weight = 2;

   // add edge 2-5 (or D-C in above figure)
   graph->edge[5].src = 2;
   graph->edge[5].dest = 5;
   graph->edge[5].weight = 1;

   // add edge 3-2 (or D-B in above figure)
   graph->edge[6].src = 3;
   graph->edge[6].dest = 2;
   graph->edge[6].weight = 7;

   // add edge 4-3 (or E-D in above figure)
   graph->edge[7].src = 4;
   graph->edge[7].dest = 3;
   graph->edge[7].weight = 3;

   // add edge 4-5 (or E-D in above figure)
   graph->edge[8].src = 4;
   graph->edge[8].dest = 5;
   graph->edge[8].weight = -4;

   // add edge 5-3 (or E-D in above figure)
   graph->edge[9].src = 4;
   graph->edge[9].dest = 5;
   graph->edge[9].weight = -1;  
  
   BellmanFord(graph, 0);

   return 0;
}
  

Sample output:

Phase 0:
Vertex    Distance from Source
--------------------------
0        0
1        10
2        5
3        10
4        7
5        3

Phase 1:
Vertex    Distance from Source
--------------------------
0        0
1        10
2        5
3        10
4        7
5        3

Phase 2:
Vertex    Distance from Source
--------------------------
0        0
1        10
2        5
3        10
4        7
5        3

Phase 3:
Vertex    Distance from Source
--------------------------
0        0
1        10
2        5
3        10
4        7
5        3

Phase 4:
Vertex    Distance from Source
--------------------------
0        0
1        10
2        5
3        10
4        7
5        3

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---