### Shortest path and double cost edge

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
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.
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.
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.

Last edited on
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?
Last edited on
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.

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244`` ``````#include #include #include #include #include #include #include #include using namespace std; const double LARGE = numeric_limits::max(); //====================================================================== struct Edge; // Forward definition struct Vertex { string id; vector edges; double distance = LARGE; Vertex *prev = nullptr; }; struct Edge { Vertex *v1, *v2; double weight; }; struct Graph { vector vertices; vector 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 &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 &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, 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 &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 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 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```

Last edited on
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.
Topic archived. No new replies allowed.