Programming language: C++ C Home | Chegg.com × / D s18 Proiect 5.pdt (- , c Secu

Question

Programming language: C++

C Home | Chegg.com × / D s18 Proiect 5.pdt (- , c Secure I https://ualearn.blackboard. d-346/465-dt-content-rid-30/86314 1/courses/18381.201810/518%20Project%205.pdf Suppose that you are searching for an airline flight. You will be interested in the price of the flight, but you will probably also be interested in the amount of time that the flight(s) will take. This program is based on that problem. You will be given a directed graph where each edge has a cost and a duration. Your job will be to find the shortest duration path that doesn't go over a given total cost. The groph will be given as follows. The number of vertices and cdges will be on the first line, followed by one edge per line. Each edge will have the two vertices, the cost and the duration, all of which will be positive integers. Note that in this graph there may be multiple edges between any two vertices. Your program should take four command line arguments: the name of the file containing the graph, the start vertex, the end vertex, and the maximum total cost. The output of the program is a single integer, the duration of the cheapest path from the start vertex to the end vertex with total cost less than the limit. If no path exists with cost less than the limit, output a 0. No other output should appear Hint: for this program, you will want to modify the Bellman-Ford algorithm. Instead of a single weight for each vertex of the graph, you will need to maintain an ordered list based on cost. Example input graph: 5 7 0130 100 04 50 125 1 2 250 50 1 2 50 150 4 2 40100 2 3 60 90 4 3 150 125 Executing projects graph.txt 0 3 200 Should output 250 Executing project5 graph.txt 0 3 140 Should output 340 Executing project5 graph.txt 0 3 139 Should output 0 3:0 PM O Type here to search 4/28/2018 2

Explanation / Answer

#include<iostream>

#include<string>

#include<fstream>

#include<vector>

using namespace std;

struct Edge

{

int src, dest, cost,duration;

};

// 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 = new Graph;

graph->V = V;

graph->E = E;

graph->edge = new Edge[E];

return graph;

}

// 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 dest, int costLimit, int &totalDuration)

{

int V = graph->V;

int E = graph->E;

int *dist = new int[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] = graph->edge[src].cost;

// 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 cost = graph->edge[j].cost;

int dur = graph->edge[j].duration;

if (dist[u] != INT_MAX && dist[u] + cost < costLimit) {

dist[v] = dist[u] + cost;

totalDuration += dur;

}

}

}

//// 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 cost = graph->edge[i].cost;

int dur = graph->edge[i].duration;

if (dist[u] != INT_MAX && dist[u] + cost < dist[v])

printf("Graph contains negative weight cycle");

}

}

// Driver program to test above functions

int main(int argc, char*argv[])

{

if (argc < 5) {

cout << "Not valid argument";

return 1;

}

int V; // Number of vertices in graph

int E; // Number of edges in graph

vector<Edge> v;

int source = atoi(argv[2]);

int destination = atoi(argv[3]);

int cost = atoi(argv[4]);

string line;

ifstream myfile(argv[1]);

int i = 0;

if (myfile.is_open()){

while (getline(myfile, line)){

if (i == 0) {

char *token = strtok(const_cast<char*>(line.c_str()), " ");

V = atoi(token);

token = strtok(NULL, " ");

E = atoi(token);

}

else

{

int j = 0;

int s, e, c, dur;

char *token = strtok(const_cast<char*>(line.c_str()), " ");

while (token!=NULL)

{

if (j == 0)

s = atoi(token);

else if(j == 1)

e = atoi(token);

else if(j == 2)

c = atoi(token);

else if(j == 3)

dur = atoi(token);

token = strtok(NULL, " ");

j++;

}

Edge ed = { s,e,c,dur };

v.push_back(ed);

}

i++;

}

myfile.close();

}

else cout << "Unable to open file";

/* Let us create the graph given in above example */

struct Graph* graph = createGraph(V, E);

int index = 0;

for (auto it = v.begin(); it != v.end(); it++) {

graph->edge[index].src = it->src;

graph->edge[index].dest = it->dest;

graph->edge[index].cost = it->cost;

graph->edge[index].duration = it->duration;

index++;

}

int duration=0;

BellmanFord(graph, source, destination,cost,duration);

if (duration < cost)

cout << duration << endl;

else

cout << "0" << endl;

system("pause");

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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