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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
#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



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.