Hi guys, I need a fix to debug it. can you help me to fix it This is a cpp file
ID: 3719336 • Letter: H
Question
Hi guys, I need a fix to debug it. can you help me to fix it
This is a cpp file
#include<iostream>
#include<vector>
#include<string>
#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 v, w, 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;
int count = 1;
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";
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;
}
and this is a text file
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
thanks
#this should be compiled by window visual studio#
Explanation / Answer
I've added two headers. And I'm able to complie now with g++
For visual studio please add stdfax header corresponding to your version of VS.
#include<iostream>
#include<vector>
#include<string>
#include<list>
#include<algorithm>
#include<fstream>
//I've added following two lines
#include<limits.h>
#include<string.h>
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 v, w, 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;
int count = 1;
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";
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;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.