Shortest path and double cost edge

[sonar87]

The code I have successfully finds the shortest path when the distance both ways from one node to an adjacent is the same in both directions, but if say going from v1 to v2 costs 3 and going from v2 to v1 costs 4, then it doesn't work, On test file it still uses the higher cost for going the direction opposite that it should be traversing.

Graph and problem output:

https://i.imgur.com/jWGMADX.png


https://codepad.remoteinterview.io/NBZWHJVTTQ

[helios]

The distance displayed is wrong, but the paths found for each of the other vertices are indeed the shortest, so it seems you're doing one thing to measure the distance and another to find the path. When asked for a distance, just find the path and then measure its length.

[sonar87]

Yea because whether it uses the incorrect value of 5 or not it's still the shortest path. But for some reason even going from 4 to 1, it's using the value for going from 1 to 3, not the value of 1 for going from 3 to 1.

[lastchance]

Is this going to work?

You don't (and I'm not sure that you could, but someone please correct me if necessary) change the position in the priority_queue AFTER all the elements have been inserted ... yet you need to adjust the order every time you change the distance of a vertex from the source.

Why not just put the vertices in a (diminishing) vector and re-sort the remaining ones (using distance-from-source) at the start of every pass of Dijkstra's algorithm? Or, better still, use a set, removing and reinserting when you change distance, so that it always remains sorted by distance.

BTW, why not post the whole code in the forum, instead of an uncompileable snippet on a remote site.

[ne555]

you are reading it backwards.
you chose 1 as the source, as the start point.

> BTW, why not post the whole code in the forum, instead of an uncompileable
> snippet on a remote site.
so it can be silently removed, as done before
http://www.cplusplus.com/forum/general/231703/


to keep the priority queue updated
http://www.cplusplus.com/reference/algorithm/make_heap/
that's O(V), where using a set will be O(N lg V) where N is the number of neighbours
dunno which is better.

another option is to simply add new vertices instead of updating the existing ones, ¿but how big may it grow?

[lastchance]

Hello @ne555,
Here is my version using alternative methods: priority queue (with additional vertices during the search) or a set.

It doesn't correspond to the OP's format as he didn't publish enough of his code.

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <limits>
using namespace std;


const double LARGE = numeric_limits<double>::max();


//======================================================================

struct Edge;                 // Forward definition


struct Vertex
{
   string id;
   vector<Edge *> edges;
   double distance = LARGE;
   Vertex *prev = nullptr;
};


struct Edge
{
   Vertex *v1, *v2;
   double weight;
};


struct Graph
{
   vector<Vertex> vertices;
   vector<Edge> edges;
   Graph() {};
   Graph( string filename );
   void write();
};


Graph::Graph( string filename )                       // Create a graph using data in file
{
   int n;
   int i, j;
   double w;

   ifstream in( filename );
   in >> n;

   vertices.resize( n );
   for ( i = 0; i < n; i++ ) vertices[i].id = to_string( i + 1 );         // Vertex index from 0, ID from 1 (unfortunately)
   while ( in >> i >> j >> w ) edges.push_back( { &vertices[i - 1], &vertices[j - 1], w } );

   for ( Edge &e : edges ) e.v1->edges.push_back( &e );
}


void Graph::write()
{
   cout << "Number of vertices = " << vertices.size() << '\n';
   cout << "Number of edges = "    << edges.size()    << '\n';
                                                  
   cout << "Vertex list:\n";
   for ( Vertex v : vertices ) cout << v.id << '\n';
                                                  
   cout << "Edge list:\n";
   for ( Edge e : edges ) cout << e.v1->id << ' ' << e.v2->id << ' ' << e.weight << '\n';

   cout << '\n';
}


//======================================================================


void printPath( const vector<Vertex *> &path )
{
   cout << path[0]->id;
   for ( int i = 1; i < path.size(); i++ ) cout << " -> " << path[i]->id;
   cout << '\n';
}


//======================================================================


struct greaterDistance
{
   bool operator() ( Vertex *a, Vertex *b ) { return a->distance > b->distance; }
};


//======================================================================


double shortestPath( Graph &g, int start, int finish, vector<Vertex *> &path )
{
   Vertex *v1, *v2;
   double d1, d2;

   // Initialise distances and path
   for ( Vertex &v : g.vertices )                     
   {
      v.distance = LARGE;
      v.prev = nullptr;
   }
   g.vertices[start].distance = 0;                   


   // Create a collection of pointers to vertices, sorted by distance from source
   priority_queue<Vertex *, vector<Vertex *>, greaterDistance> work;   
   for ( Vertex &v : g.vertices ) work.push( &v );                     


   // Loop Dijkstra's algorithm
   while ( !work.empty() )
   {
      v1 = work.top();                                // Add the current shortest-distance vertex to those finalised
      work.pop();                                     //    by removing it from the priority queue
      if ( v1 == &g.vertices[finish] ) break;         // Finished if we have finalised the designated node

      d1 = v1->distance;
      for ( Edge *e : v1->edges )                     // Update any minimum distances via this node
      {                                               
         d2 = d1 + e->weight;
         v2 = e->v2;
         if ( v2->distance > d2 )
         {
            v2->distance = d2;
            v2->prev = v1;
            work.push( v2 );                          // ADDS ANOTHER COPY (with different priority)
         }
      }
   }


   // Create the path back to the source
   path.clear();                        
   path.push_back( v1 );
   while ( v1->prev != nullptr )
   {
      v1 = v1->prev;
      path.push_back( v1 );
   }
   reverse( path.begin(), path.end() );


   return path.back()->distance;
}


//======================================================================


struct lessDistance
{
   bool operator() ( Vertex *a, Vertex *b ) { return a->distance < b->distance; }
};


//======================================================================


double shortestPath_Set( Graph &g, int start, int finish, vector<Vertex *> &path )
{
   Vertex *v1, *v2;
   double d1, d2;

   // Initialise distances and path
   for ( Vertex &v : g.vertices )
   {
      v.distance = LARGE;
      v.prev = nullptr;
   }
   g.vertices[start].distance = 0;                    


   // Create a collection of pointers to vertices, sorted by distance from source
   set<Vertex *, lessDistance> work;
   for ( Vertex &v : g.vertices ) work.insert( &v );


   // Loop Dijkstra's algorithm
   while ( !work.empty() )
   {
      v1 = *work.begin();                             // Add the current shortest-distance vertex to those finalised
      work.erase( work.begin() );                     //    by removing it from the set
      if ( v1 == &g.vertices[finish] ) break;         // Get out if we have finalised the designated node

      d1 = v1->distance;
      for ( Edge *e : v1->edges )                     // Update any minimum distances via this node
      {                                               
         d2 = d1 + e->weight;
         v2 = e->v2;
         if ( v2->distance > d2 )
         {
            v2->distance = d2;
            v2->prev = v1;
            work.erase( v2 );                         // REINSERT with new distance
            work.insert( v2 );                        //
         }
      }
   }


   // Create the path back to the source
   path.clear();
   path.push_back( v1 );
   while ( v1->prev != nullptr )
   {
      v1 = v1->prev;
      path.push_back( v1 );
   }
   reverse( path.begin(), path.end() );

   return path.back()->distance;
}


//======================================================================


int main()
{
   Graph g( "input.txt" );
   g.write();

   int a, b;
   vector<Vertex *> path;
   cout << "Input node ids for start and finish: ";   cin >> a >> b;
   cout << "Shortest distance (p-q): " << shortestPath    ( g, a - 1, b - 1, path ) << '\n';
   cout << "Path: ";   printPath( path );

   cout << "Shortest distance (set): " << shortestPath_Set( g, a - 1, b - 1, path ) << '\n';
   cout << "Path: ";   printPath( path );
}


//====================================================================== 

input.txt:

4 
1 3 5 
3 2 4
2 4 1
1 2 12
3 1 1
2 3 4
4 2 1
2 1 12

Output:

Number of vertices = 4
Number of edges = 8
Vertex list:
1
2
3
4
Edge list:
1 3 5
3 2 4
2 4 1
1 2 12
3 1 1
2 3 4
4 2 1
2 1 12

Input node ids for start and finish: 1 4
Shortest distance (p-q): 10
Path: 1 -> 3 -> 2 -> 4
Shortest distance (set): 10
Path: 1 -> 3 -> 2 -> 4

...
Input node ids for start and finish: 4 1
Shortest distance (p-q): 6
Path: 4 -> 2 -> 3 -> 1
Shortest distance (set): 6
Path: 4 -> 2 -> 3 -> 1

[sonar87]

Hmm I just thought that syntax highlighting of that thin made it easier to go through and take a quick look at so it would be easier to help. Guess that pads don't stay around as long as I thought.