Hi, I have a little problem with my C++ code. I am asking since 2 days before an
ID: 3720023 • Letter: H
Question
Hi, I have a little problem with my C++ code. I am asking since 2 days before and nobody could provide me the right answer. The first data output it displays correctly but the second data output my program did not make the correct calculation as specified in the requeriments. Also, my program did not display the names of the airports from the minimum path it only displays "Total path: 1120" and it should display "Min Path: SF LA LONDON PARIS 920." Please provide a screenshot and I will rate your answer thanks.
Requeriments test data 2 expected output:
Data Set 1: Test Run 2
Enter Start Vertex: SF
Enter End Vertex : PARIS
Min Path: SF LA LONDON PARIS 920
My Wrong Output:
Enter Start Vertex : SF
Enter End Vertex : PARIS
Total path: 1120
Code:
#include <iostream>
#include <cstdlib>
#include <cctype>
#include <vector>
#include <limits.h>
#include <string>
#include <cstring>
#include <list>
#include <algorithm>
#include <fstream>
using namespace std;
void addEdge(vector <pair<int, int> > adj[], int u, int v, int wt)
{
adj[u].push_back(make_pair(v, wt));
adj[v].push_back(make_pair(u, wt));
}
// Print adjacency list representaion ot graph
void printGraph(vector<pair<int, int> > adj[], int V)
{
int v, w;
for (int u = 0; u < V; u++)
{
cout << u << " - ";
for (auto it = adj[u].begin(); it != adj[u].end(); it++)
{
v = it->first;
w = it->second;
cout << v << " ="
<< w << " ";
}
cout << " ";
}
}
// This function mainly does BFS and prints the
// shortest path from src to dest. It is assumed
// that weight of every edge is 1
void findShortestPath(vector<pair<int, int>> adj[], int src, int dest, int V, int &total)
{
// Mark all the vertices as not visited
bool *visited = new bool[2 * V];
int *parent = new int[2 * V];
// Initialize parent[] and visited[]
for (int i = 0; i < 2 * V; i++)
{
visited[i] = false;
parent[i] = -1;
}
// Mark the current node as visited and enqueue it
visited[src] = true;
int smallest = INT_MAX;
for (int u = 0; u < V - 1; u++)
{
smallest = INT_MAX;
for (int j = 0; j < adj[u].size() - 1; j++)
{
if (adj[u][j].second < adj[u][j + 1].second && visited[adj[u][j].first] == false)
{
if (adj[u][j].second < smallest)
{
smallest = adj[u][j].second;
visited[adj[u][j].first] = true;
}
}
else if (visited[adj[u][j + 1].first] == false)
{
if (adj[u][j + 1].second < smallest)
{
smallest = adj[u][j + 1].second;
visited[adj[u][j + 1].first] = true;
}
}
if (adj[u][j].first == dest)
{
total += adj[u][j].second;
return;
}
else if (adj[u][j + 1].first == dest)
{
total += adj[u][j + 1].second;
return;
}
}
total += smallest;
}
}
// Driver code
int main()
{
vector<pair<int, int>> adj[6];
int V = 6;
string line;
ifstream myfile("file.txt");
vector<string> vertex;
if (myfile.is_open())
{
while (getline(myfile, line))
{
// cout << line << ' ';
while (line != "-1")
{
char *token = strtok(const_cast<char *>(line.c_str()), " ");
token = strtok(NULL, " ");
vertex.push_back(token);
getline(myfile, line);
// cout << line << ' ';
}
V = vertex.size();
getline(myfile, line);
//cout << line << ' ';
while (line != "-1")
{
char *token = strtok(const_cast<char *>(line.c_str()), " ");
int u = atoi(token);
int v = atoi(strtok(NULL, " "));
int w = atoi(strtok(NULL, " "));
addEdge(adj, u, v, w);
getline(myfile, line);
// cout << line << ' ';
}
}
myfile.close();
}
else {
cout << "Unable to open file";
exit(1);
}
string start, end;
cout << "Enter Start Vertex : ";
cin >> start;
cout << "Enter End Vertex : ";
cin >> end;
int s, e;
int i = 0;
for (auto it = vertex.begin(); it != vertex.end(); it++)
{
if (*it == start)
s = i;
if (*it == end)
e = i;
i++;
}
// printGraph(adj, V);
int total = 0;
findShortestPath(adj, s, e, V, total);
cout << "Total path: " << total << endl;
printGraph(adj, V);
system("pause");
return 0;
}
File Required to run the program:
0 SF
1 LA
2 CHICAGO
3 NY
4 PARIS
5 LONDON
-1
0 1 80
0 2 200
0 3 300
1 2 230
1 5 700
2 3 180
3 4 630
3 5 500
4 5 140
-1
Explanation / Answer
HI,
i have modified the code and fixed the problem and added comments
#include <iostream>
#include <cstdlib>
#include <cctype>
#include <vector>
#include <limits.h>
#include <string>
#include <cstring>
#include <list>
#include <algorithm>
#include <fstream>
using namespace std;
void addEdge(vector <pair<int, int> > adj[], int u, int v, int wt)
{
adj[u].push_back(make_pair(v, wt));
adj[v].push_back(make_pair(u, wt));
}
// Print adjacency list representaion ot graph
void printGraph(vector<pair<int, int> > adj[], int V)
{
int v, w;
for (int u = 0; u < V; u++)
{
cout << u << " - ";
for (auto it = adj[u].begin(); it != adj[u].end(); it++)
{
v = it->first;
w = it->second;
cout << v << " ="
<< w << " ";
}
cout << " ";
}
}
// This function mainly does BFS and prints the
// shortest path from src to dest. It is assumed
// that weight of every edge is 1
void findShortestPath(vector<pair<int, int>> adj[], int src, int dest, int V, int &total)
{
// Mark all the vertices as not visited
bool *visited = new bool[2 * V];
int *parent = new int[2 * V];
// Initialize parent[] and visited[]
for (int i = 0; i < 2 * V; i++)
{
visited[i] = false;
parent[i] = -1;
}
// Mark the current node as visited and enqueue it
visited[src] = true;
int smallest = INT_MAX;
for (int u = 0; u < V - 1; u++)
{
smallest = INT_MAX;
for (int j = 0; j < adj[u].size() - 1; j++)
{
if (adj[u][j].second <= adj[u][j + 1].second && visited[adj[u][j].first] == false)//change here from < to <=
{
if (adj[u][j].second <= smallest)//similar change here
{
smallest = adj[u][j].second;
cout<<adj[u][j].second<<endl; //printing path
visited[adj[u][j].first] = true;
}
}
else if (visited[adj[u][j + 1].first] == false)
{
if (adj[u][j + 1].second <= smallest)
{
smallest = adj[u][j + 1].second;
cout<<adj[u][j].second<<endl; //printing path
visited[adj[u][j + 1].first] = true;
}
}
if (adj[u][j].first == dest)
{
total += adj[u][j].second;
return;
}
else if (adj[u][j + 1].first == dest)
{
total += adj[u][j + 1].second;
return;
}
}
total += smallest;
}
}
// Driver code
int main()
{
vector<pair<int, int>> adj[6];
int V = 6;
string line;
ifstream myfile("file.txt");
vector<string> vertex;
if (myfile.is_open())
{
while (getline(myfile, line))
{
// cout << line << ' ';
while (line != "-1")
{
char *token = strtok(const_cast<char *>(line.c_str()), " ");
token = strtok(NULL, " ");
vertex.push_back(token);
getline(myfile, line);
// cout << line << ' ';
}
V = vertex.size();
getline(myfile, line);
//cout << line << ' ';
while (line != "-1")
{
char *token = strtok(const_cast<char *>(line.c_str()), " ");
int u = atoi(token);
int v = atoi(strtok(NULL, " "));
int w = atoi(strtok(NULL, " "));
addEdge(adj, u, v, w);
getline(myfile, line);
// cout << line << ' ';
}
}
myfile.close();
}
else {
cout << "Unable to open file";
exit(1);
}
string start, end;
cout << "Enter Start Vertex : ";
cin >> start;
cout << "Enter End Vertex : ";
cin >> end;
int s, e;
int i = 0;
for (auto it = vertex.begin(); it != vertex.end(); it++)
{
if (*it == start)
s = i;
if (*it == end)
e = i;
i++;
}
// printGraph(adj, V);
int total = 0;
findShortestPath(adj, s, e, V, total);
cout << "Total path: " << total << endl;
printGraph(adj, V);
system("pause");
return 0;
}
Thumbs up if this was helpful, otherwise let me know in comments
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.