C++ programing question24 Bellman-Ford Time Limit: 2 seconds Problem Description

Question

C++ programing question24

Bellman-Ford
Time Limit: 2 seconds

Problem Description
For a directed graph G=( V, E ), edge e corresponds to a weight w, which can be regarded as the cost of taking this edge.

try to find the shortest path between two specific points on a directed weighted graph.
Input File Format
There will be a positive integer T at the beginning, which means that there will be T input datas.
The first line of each input data has three positive integers n, m, and q, representing n points and m edges on the graph, 2 ? n ? 5000 , 1 ? m
? 20000, each point is numbered 0 ~ n-1, q is the number of queries.
The next m rows each have three positive integers u, v, and w, which represent an edge from u to v with a weight of w, -1000 ? w ?
1000.
Then there will be q rows of queries, each with two integers s and e, representing the shortest path from s to e.
Output Format
Each query outputs the answer in a separated line. If the shortest path does not exist (i.e. cannot be reached, there is a negative ring), the line outputs "No".

Explanation / Answer

Implemented Source Code:-
-------------------------
#include<iostream>
#include<fstream>
#include<stdlib.h>
using namespace std;
struct Edge
{
int source;
int destination;
int weight;
};
struct Graph
{
int V, E; // V-> Number of vertices, E-> Number of edges
struct Edge* edge;
};
class Bellman_Ford{
public:
struct Graph* createGraph(int Vertices, int Edges)
{
struct Graph* graph = new Graph;
graph->V=Vertices;
graph->E=Edges;
graph->edge = new Edge[Edges];
return graph;
};
public:
void Bellman(struct Graph* graph, int src)
{
int V = graph->V;
int E = graph->E;
int dist[V];
for(int i=0;i<V;i++)
dist[i]=INT_MAX;
dist[src]=0;
for(int i=1;i<=V-1;i++)
{
for(int j=0;j<E;j++)
{
int u = graph->edge[j].source;
int v = graph->edge[j].destination;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
for(int i=0;i<E;i++)
{
int u = graph->edge[i].source;
int v = graph->edge[i].destination;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
printf("Graph contains negative weight cycle");
}
Print_Graph(dist, V);
}
public:
void Print_Graph(int dist[], int n)
{
printf("Vertex Distance from Source ");
for (int i=0;i<n;++i)
{
printf("%d %d ", i, dist[i]);
}
}
};
int main()
{
Bellman_Ford obj;//creating an Object for Bellman_Ford class
int Vertices = 5; // Number of vertices in graph
int Edges = 8; //Number of Edges in Graph
struct Graph* graph = obj.createGraph(Vertices, Edges);
ifstream infile;
infile.open("graph.txt");
int i=0;
while(i<8)
{
infile>>graph->edge[i].source;
infile>>graph->edge[i].destination;
infile>>graph->edge[i].weight;
i++;
}
obj.Bellman(graph,0);
return 0;
}
Input file:-
-------------
3 3 2
0 2 2
1 0 5
3 0 1
5 6 3
0 2 3
1 0 10

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.