Member Avatar for wnrqkflwnrqkfl

Hi all, I asked about this question few days ago, and I have tried few things other experts told me

I think i got overcame problem where i can read the tab spaced file but now the output is the problem.....

When i run my program it outputs:

Enter filename: qantum.txt
Enter start city: Sydney

(so far its okay but...)

Cheapest price to New York = 1300

it outputs only one result where it should outputs all the city which is connected with Sydney....

The following output is what it should be:

Enter filename : qantum.txt
Enter start city : Tokyo
Cheapest price to Brussels = 700
Tokyo Paris Brussels
Cheapest price to London = 900
Tokyo Paris London
Cheapest price to Melbourne = 2200
Tokyo Paris London Sydney Melbourne
Cheapest price to New York = 500
Tokyo New York
Cheapest price to Paris = 600
Tokyo Paris
Cheapest price to Sydney = 2000
Tokyo Paris London Sydney


I'll upload my code so plz help me..

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <list>
#include <map>
#include <queue>
#include <vector>

using namespace std;

class Student
{
public:
   string name;
   double tuition;
};

//This function sorts by tuitions fees
bool SortStudentByTute ( const Student& left, const Student& right )
{
   if ( left.tuition > right.tuition )
   {
      return false;
   }
   else if ( left.tuition < right.tuition )
   {
      return true;
   }
} 

bool SortStudentByName ( const Student& left, const Student& right )
{
   //Here you can define whatever the sort criterion
   //needs to be. It can be as complicated as you wish
 
   if ( left.name > right.name )
   {
      return false;
   }
   else if ( left.name < right.name )
   {
      return true;
   }
   //else //i.e if both are equal
 
}



class Edge;

class Node
{
public:
   string    name;
   list<Edge*> neighbors;
   bool      visited;
   double       cost;
   Node      *back_pointer;

   Node ( string const &n ) : name ( n ), visited ( false ), cost ( 0 )
   {}
};

class Edge
{
public:
   double weight;
   Node * dest;

   Edge ( double c, Node *d = NULL ) : weight ( c ), dest ( d )
   {}

   ~Edge()
   {
      if ( dest ) delete dest;
   }
};

class NodeMap
{
public:
   map<string, Node*> nodemap;

   Node* find_in_nodemap ( string const &name )
   {
      Node* result = nodemap[name];
      if ( result == 0 )
      {
         result = nodemap[name] = new Node ( name );
      }
      return result;
   }
   friend ostream& operator<< ( ostream& o, NodeMap nm )
   {
      map<string, Node*>::iterator im;
      for ( im = nm.nodemap.begin(); im != nm.nodemap.end(); im++ )
      {
         //pair<string,Node*> p = *im;
         //o << p.second->name << endl;
         o << ( *im ).second->name << endl;
         list<Edge*> neighbors = ( *im ).second->neighbors;
         list<Edge*>::iterator e;
      }
      return o;
   }
};

struct compare
{

   bool operator() ( Node * &a, Node * &b ) const
   {
      // least to greatest
      return b->cost < a->cost;
   }
};
// for each solution, reset node information
void reset_nodes ( NodeMap &nm )
{
   map<string, Node*>::iterator im;
   for ( im = nm.nodemap.begin(); im != nm.nodemap.end(); im++ )
   {
      ( *im ).second->cost = 0;
      ( *im ).second->back_pointer = 0;
      ( *im ).second->visited = false;
   }
}

void dijkstra ( string s, NodeMap &nodes )
{
   Student myStudent [500]; //create an array of objects

   int i = 0;

   // check and report or abort
   Node* source = nodes.nodemap[s];
   if ( source == 0 )
   {
      cout << "Sorry we don't fly from " << s << endl;
      return;
   }
   reset_nodes ( nodes );

   // put the source into pq and loop until empty
   priority_queue<Node *, deque<Node*>, compare > pq;
   pq.push ( source );
   while ( !pq.empty() )
   {
      // process least cost node.
      Node* curr = pq.top();
      pq.pop();
      curr->visited = true;
      // process neighbors
      list<Edge*>::iterator edge; 
      for ( edge = curr->neighbors.begin(); edge != curr->neighbors.end(); edge++ )
      {
         Node *ne = ( *edge )->dest;
         if ( !ne->visited )
         {
            ne->cost += ( *edge )->weight + curr->cost;
            ne->visited = true;
            ne->back_pointer = curr;
            //cout << "Cheapest price to "<< ne->name << " = " << ne->cost << endl; 

            myStudent[i].name = ne->name;
            myStudent[i].tuition = ne->cost;
            i++; 


            pq.push ( ne );
         }
      }
   }

   std::sort ( myStudent, myStudent + i, SortStudentByName );
   for ( int j = 0; j < i; j++ )
   {
      cout << "Cheapest price to " << myStudent[j].name << " = " << myStudent[j].tuition << endl;
   }
}

void get_graph ( string const &filename, NodeMap &node_map )
{
   ifstream inf ( filename.c_str() );
   string from;
   string to;
   double weight;
   
   while ( getline(inf,from,'\t') )
   {     
         getline(inf,to,'\t');
         inf>>weight;  
         if(inf.good())
         {          
         Node *Target = node_map.find_in_nodemap ( to );
         Node *Source = node_map.find_in_nodemap ( from );
         Edge *connector = new Edge ( weight, Target );
         Source->neighbors.push_back ( connector );
         }
   }
}
int main()
{
   NodeMap nodes;
   ifstream inf;
   string filename;
   cout << "Enter filename : ";
   cin >> filename;
   inf.open ( filename.c_str() );
   get_graph ( filename, nodes );

   string s;
   cout << "Enter start city : ";
   cin >> s;
   dijkstra ( s, nodes );

   system ( "PAUSE" );
   return 0;
}
Sydney NewYork	1300
NewYork Paris 1200
London Sydney 1100
Sydney London 1300
Paris NewYork 900
NewYork London 700
London Paris 200
Sydney Paris 900
Paris London 300
Brussels Paris 200
London Brussels 300
Sydney Brussels 700
Brussels NewYork 400
Paris Brussels 100
Tokyo NewYork 500
Tokyo Paris 600
Sydney Tokyo 300
Sydney Melbourne 200
  • 2 Contributors
  • 2 Replies
  • 100 Views
  • 11 Hours Discussion Span
  • Latest Post Latest Post by daviddoria

Dani AI

Generated

Two directions to check quickly (based on 's symptom and 's suggestion to extract a minimal example): the program is either not parsing the tab-separated file reliably, or the graph/printing logic stops early or only records one path. Common, hard-to-see culprits are leftover CR characters from Windows line endings, mixing operator>> and std::getline (leaving a stray newline in the input buffer), or a break/return inside the loop that prints results.

Recommendations and small, safe snippets to try:

  • Verify the file is parsed exactly as expected: print every token after parsing to confirm source, destination, and cost are read correctly and that no trailing \r remains. Remove \r and trim whitespace before using strings as map keys.
  • Avoid mixing >> and getline without clearing the input buffer. Use std::getline(std::cin >> std::ws, line) or call std::cin.ignore(...) when switching forms of input.
  • Compute single-source shortest paths once (e.g., Dijkstra) from the start city; then iterate the distance/parent tables to print all reachable cities and their reconstructed paths. That avoids re-running or accidentally only showing the first found path.

Parsing + trimming example:

#include <string>
#include <sstream>
#include <algorithm>
#include <cctype>

static inline std::string trim(std::string s) {
    s.erase(s.begin(), std::find_if(s.begin(), s.end(),
        [](unsigned char ch){ return !std::isspace(ch); }));
    s.erase(std::find_if(s.rbegin(), s.rend(),
        [](unsigned char ch){ return !std::isspace(ch); }).base(), s.end());
    return s;
}

// parse one tab-separated line: "src<TAB>dest<TAB>cost"
void parse_line(const std::string &line) {
    std::string l = line;
    if (!l.empty() && l.back() == '\r') l.pop_back(); // strip Windows CR
    std::istringstream iss(l);
    std::string src, dest, cost;
    std::getline(iss, src, '\t');
    std::getline(iss, dest, '\t');
    std::getline(iss, cost);
    src = trim(src); dest = trim(dest); cost = trim(cost);
    // debug print: confirm tokens and store into graph structure
}

After running your shortest-path routine, reconstruct every path from the parent table and print cost + route (run Dijkstra once, then loop all nodes to build their route). For reference on reliable line-reading behavior, see std::getline on cppreference and for the single-source shortest-path pattern, see Dijkstra's algorithm on Wikipedia.

If parsing prints the expected edges and the adjacency lists look correct but output still shows only a single city, inspect any break, return, or loop-condition logic in the result-printing block and ensure the parent/distance containers are not accidentally reinitialized or cleared inside that loop.

Recommended Answers

All 2 Replies

Member Avatar for wnrqkflwnrqkfl

Oops sorry dont know y but it only works like that when i type Sydney rest city says "Press any key to continue" right away!!!

plz help me with this first...

Member Avatar for daviddoria

If possible, can you extract the problematic part of the code and post it so we don't have to download a file? Maybe you can make a very small example that demonstrates the problem without having the overhead of the rest of the code.

Dave

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.