Databases
StackOverflow2013
Postsdbo
POApplying Dijkstra's algorithm on a graph of five nodes
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POApplying Dijkstra's algorithm on a graph of five nodes
    primarykey
    data
    text
    <p>Last week, I posted a piece of code to apply Dijkstra's algorithm to calculate the shortest path between to nodes in a graph. I've made some improvements but still stuck.</p> <p>I have a class <code>Graph</code>. It shall be constructed by two other classes: a vector of instances of a class <code>Edge</code>, and another vector of elements of class <code>Vertex</code>. Every vertex has an ID and a <code>carried</code> to keep the accumulated distance from the source node, and every edge has two vertices and a weight.</p> <p>Class <code>Graph</code> has a method; its name is <code>shortest</code> and it takes two vertices as arguments: the first one is the source of the graph and the second is for the destination.</p> <p>My approach is trying to eliminate the edges that are connected to the source vertex, and adding their weights to the adjacent vertices, saving them in <code>carried</code>, a field in <code>Vertex</code> to keep tracking the situation of every vertex. Then we'd select the lowest vertex base on its <code>carried</code> to be a new source and repeat the same operation over and over till we end up with just one edge. </p> <p>To demonstrate the result, I initialized a graph which has five vertices <code>vers[0], vers[1], vers[2], vers[3], vers[4]</code>, and there are 10 edges connecting those vertices starting from <code>eds[0], eds[1], ....eds[9]</code>.</p> <p>The destination vertex is <code>vers[4]</code> while the source vertex <code>vers[2]</code> is connected by 4 edges, so when applying the method <code>shortest</code>, as is shown in the code below, I should get rid of all 4 of those edges and end up with 6 edges at the end of the first round. The result is as follows:</p> <pre><code>Hello, This is a graph 0____1 5 0____3 4 0____4 6 1____3 5 1____4 7 3____4 3 size of edges 6 size of vertices 4 curried vertex_0 9 curried vertex_1 2 curried vertex_2 1 curried vertex_3 8 </code></pre> <p>As we can see that the result looks good so far because we don't see the the source vertex which is 2 and we ended up with just 6 edges after eliminating the four edges connected to the source vertex. Plus we have to do the right hand side, or the weight of every edge, and down we have the <code>carried</code> of each remaining vertex.</p> <p>Now if we do the second round, we get the following result:</p> <pre><code>Hello, This is a graph 0____1 5 0____4 6 1____4 7 size of edges 3 size of vertices 3 curried vertex_0 9 curried vertex_1 2 curried vertex_2 8 </code></pre> <p>As you can see we got 3 edges left (which is correct) and three vertices (also correct), and the weights of the edges are correct, but the problem is that I got incorrect <code>carried</code> values for each vertex and that will make the code select a wrong source to continue with in following rounds. Namely, we should have <code>5, 2, 4</code> instead of <code>9, 2, 8</code>.</p> <p>I can see where the problem is but I don't understand why I am not getting the right solution. I think the problem is located between the asterisked lines shown in the code.</p> <p>Here is the code:</p> <pre><code>#include&lt;iostream&gt; #include&lt;vector&gt; #include &lt;stdlib.h&gt; // for rand() using namespace std; class Vertex { private: unsigned int id; // the name of the vertex unsigned int carried; // the weight a vertex may carry when calculating shortest path public: unsigned int get_id(){return id;}; unsigned int get_carried(){return carried;}; void set_id(unsigned int value) {id = value;}; void set_carried(unsigned int value) {carried = value;}; inline bool operator==( const Vertex&amp; ver_1){ return id == ver_1.id;}; Vertex(unsigned int init_val = 0, unsigned int init_carried = 0) :id (init_val), carried(init_carried) // constructor {} ~Vertex() {}; // destructor }; class Edge { private: Vertex first_vertex; // a vertex on one side of the edge Vertex second_vertex; // a vertex on the other side of the edge unsigned int weight; // the value of the edge ( or its weight ) public: unsigned int get_weight() {return weight;}; void set_weight(unsigned int value) {weight = value;}; Vertex get_ver_1(){return first_vertex;}; Vertex get_ver_2(){return second_vertex;}; void set_first_vertex(Vertex v1) {first_vertex = v1;}; void set_second_vertex(Vertex v2) {second_vertex = v2;}; Edge(const Vertex&amp; vertex_1 = 0, const Vertex&amp; vertex_2 = 0, unsigned int init_weight = 0) : first_vertex(vertex_1), second_vertex(vertex_2), weight(init_weight) {} ~Edge() {} ; // destructor }; class Graph { private: std::vector&lt;Vertex&gt; vertices; std::vector&lt;Edge&gt; edges; public: Graph(vector&lt;Vertex&gt; ver_vector, vector&lt;Edge&gt; edg_vector) : vertices(ver_vector), edges(edg_vector){} ~Graph() {} vector&lt;Vertex&gt; get_vertices(){return vertices;} vector&lt;Edge&gt; get_edges(){return edges;} void set_vertices(vector&lt;Vertex&gt; vector_value) {vertices = vector_value;} void set_edges(vector&lt;Edge&gt; vector_ed_value) {edges = vector_ed_value;} unsigned int shortest(Vertex src, Vertex dis); }; unsigned int Graph::shortest(Vertex src, Vertex dis) { vector&lt;Vertex&gt; ver_out; vector&lt;Edge&gt; track; for (unsigned int i = 0; i &lt; edges.size();) { if ((edges[i].get_ver_1() == src) || (edges[i].get_ver_2() == src)) { track.push_back(edges[i]); if (edges[i].get_ver_1() == src) { ver_out.push_back(edges[i].get_ver_2()); ver_out.back().set_carried(edges[i].get_weight()); } else { ver_out.push_back(edges[i].get_ver_1()); ver_out.back().set_carried(edges[i].get_weight()); } edges.erase(edges.begin() + i); } else { ++i; // increment only if not erasing } } for(unsigned int i = 0; i &lt; vertices.size(); ++i) for(unsigned int iii = 0; iii &lt; ver_out.size(); ++iii) { if(vertices[i] == ver_out[iii]){vertices[i].set_carried(ver_out[iii].get_carried());};}; for(unsigned int i = 0; i &lt; vertices.size(); ++i) if(vertices[i] == src) vertices.erase(vertices.begin() + i); track.clear(); if(!(ver_out[0] == dis)) {src = ver_out[0];} else {src = ver_out[1];} for(unsigned int i = 0; i &lt; ver_out.size(); ++i) if((ver_out[i].get_carried() &lt; src.get_carried()) &amp;&amp; (!(ver_out[i] == dis))) src = ver_out[i]; ver_out.clear(); for(unsigned int round = 0; round &lt; 1 ; ++round) //vertices.size() { for(unsigned int k = 0; k &lt; edges.size(); ) { if((edges[k].get_ver_1() == src) || (edges[k].get_ver_2() == src)) { track.push_back (edges[k]); for(unsigned int i = 0; i &lt; vertices.size(); ++i) { if(track.back().get_ver_1() == vertices[i]) edges[k].get_ver_1().set_carried(vertices[i].get_carried()); if(track.back().get_ver_2() == vertices[i]) edges[k].get_ver_2().set_carried(vertices[i].get_carried()); } if(track.back().get_ver_1() == src) { ver_out.push_back (track.back().get_ver_2()); //************************************ if(track.back().get_ver_2().get_carried() &gt; (track.back().get_ver_1().get_carried() + track.back().get_weight())) //&lt;=== ver_out.back().set_carried(track.back().get_ver_1().get_carried() + track.back().get_weight()); else ver_out.back().set_carried(track.back().get_ver_2().get_carried()); } else{ ver_out.push_back (track.back().get_ver_1()); if(track.back().get_ver_1().get_carried() &gt; (track.back().get_ver_2().get_carried() + track.back().get_weight())) // &lt;=== ver_out.back().set_carried(track.back().get_ver_2().get_carried() + track.back().get_weight()); else {ver_out.back().set_carried(track.back().get_ver_1().get_carried());} } //***************************** edges.erase(edges.begin() + k); } else{ ++k; // increment only if not erasing } }; for(unsigned int t = 0; t &lt; vertices.size(); ++t) if(vertices[t] == src) vertices.erase(vertices.begin() + t); track.clear(); if(!(ver_out[0] == dis)) {src = ver_out[0];} else {src = ver_out[1];} for(unsigned int tt = 0; tt &lt; edges.size(); ++tt) { if(ver_out[tt].get_carried() &lt; src.get_carried()) { src = ver_out[tt]; } } ver_out.clear(); } if(edges[0].get_ver_1() == dis) return edges[0].get_weight() +edges[0].get_ver_2().get_carried(); else return edges[0].get_weight() +edges[0].get_ver_1().get_carried(); } int main() { cout&lt;&lt; "Hello, This is a graph"&lt;&lt; endl; vector&lt;Vertex&gt; vers(5); vers[0].set_id(0); vers[1].set_id(1); vers[2].set_id(2); vers[3].set_id(3); vers[4].set_id(4); vector&lt;Edge&gt; eds(10); eds[0].set_first_vertex(vers[0]); eds[0].set_second_vertex(vers[1]); eds[0].set_weight(5); eds[1].set_first_vertex(vers[0]); eds[1].set_second_vertex(vers[2]); eds[1].set_weight(9); eds[2].set_first_vertex(vers[0]); eds[2].set_second_vertex(vers[3]); eds[2].set_weight(4); eds[3].set_first_vertex(vers[0]); eds[3].set_second_vertex(vers[4]); eds[3].set_weight(6); eds[4].set_first_vertex(vers[1]); eds[4].set_second_vertex(vers[2]); eds[4].set_weight(2); eds[5].set_first_vertex(vers[1]); eds[5].set_second_vertex(vers[3]); eds[5].set_weight(5); eds[6].set_first_vertex(vers[1]); eds[6].set_second_vertex(vers[4]); eds[6].set_weight(7); eds[7].set_first_vertex(vers[2]); eds[7].set_second_vertex(vers[3]); eds[7].set_weight(1); eds[8].set_first_vertex(vers[2]); eds[8].set_second_vertex(vers[4]); eds[8].set_weight(8); eds[9].set_first_vertex(vers[3]); eds[9].set_second_vertex(vers[4]); eds[9].set_weight(3); unsigned int path; Graph graf(vers, eds); path = graf.shortest(vers[2], vers[4]); cout&lt;&lt;graf.get_edges()[0].get_ver_1().get_id() &lt;&lt;"____"&lt;&lt;graf.get_edges()[0].get_ver_2().get_id() &lt;&lt;" "&lt;&lt;graf.get_edges()[0].get_weight()&lt;&lt; endl; //test cout&lt;&lt;graf.get_edges()[1].get_ver_1().get_id() &lt;&lt;"____"&lt;&lt;graf.get_edges()[1].get_ver_2().get_id() &lt;&lt;" "&lt;&lt;graf.get_edges()[1].get_weight()&lt;&lt; endl; //test cout&lt;&lt;graf.get_edges()[2].get_ver_1().get_id() &lt;&lt;"____"&lt;&lt;graf.get_edges()[2].get_ver_2().get_id() &lt;&lt;" "&lt;&lt;graf.get_edges()[2].get_weight()&lt;&lt; endl; //test //cout&lt;&lt;graf.get_edges()[3].get_ver_1().get_id() &lt;&lt;"____"&lt;&lt;graf.get_edges()[3].get_ver_2().get_id() &lt;&lt;" "&lt;&lt;graf.get_edges()[3].get_weight()&lt;&lt; endl; //test //cout&lt;&lt;graf.get_edges()[4].get_ver_1().get_id() &lt;&lt;"____"&lt;&lt;graf.get_edges()[4].get_ver_2().get_id() &lt;&lt;" "&lt;&lt;graf.get_edges()[4].get_weight()&lt;&lt; endl; //test //cout&lt;&lt;graf.get_edges()[5].get_ver_1().get_id() &lt;&lt;"____"&lt;&lt;graf.get_edges()[5].get_ver_2().get_id() &lt;&lt;" "&lt;&lt;graf.get_edges()[5].get_weight()&lt;&lt; endl; //test //cout&lt;&lt;graf.get_edges()[6].get_ver_1().get_id() &lt;&lt;"____"&lt;&lt;graf.get_edges()[6].get_ver_2().get_id() &lt;&lt;" "&lt;&lt;graf.get_edges()[6].get_weight()&lt;&lt; endl; //test //cout&lt;&lt;graf.get_edges()[7].get_ver_1().get_id() &lt;&lt;"____"&lt;&lt;graf.get_edges()[7].get_ver_2().get_id() &lt;&lt;" "&lt;&lt;graf.get_edges()[7].get_weight()&lt;&lt; endl; //test //cout&lt;&lt;graf.get_edges()[8].get_ver_1().get_id() &lt;&lt;"____"&lt;&lt;graf.get_edges()[8].get_ver_2().get_id() &lt;&lt;" "&lt;&lt;graf.get_edges()[8].get_weight()&lt;&lt; endl; //test //cout&lt;&lt;graf.get_edges()[9].get_ver_1().get_id() &lt;&lt;"____"&lt;&lt;graf.get_edges()[9].get_ver_2().get_id() &lt;&lt;" "&lt;&lt;graf.get_edges()[9].get_weight()&lt;&lt; endl; //test cout&lt;&lt;"size of edges "&lt;&lt;graf.get_edges().size()&lt;&lt; endl; cout&lt;&lt;"size of vertices "&lt;&lt;graf.get_vertices().size()&lt;&lt; endl; cout&lt;&lt;"curried vertex_0 "&lt;&lt;graf.get_vertices()[0].get_carried()&lt;&lt; endl; cout&lt;&lt;"curried vertex_1 "&lt;&lt;graf.get_vertices()[1].get_carried()&lt;&lt; endl; cout&lt;&lt;"curried vertex_2 "&lt;&lt;graf.get_vertices()[2].get_carried()&lt;&lt; endl; //cout&lt;&lt;"curried vertex_3 "&lt;&lt;graf.get_vertices()[3].get_carried()&lt;&lt; endl; //cout&lt;&lt; path &lt;&lt; endl; return 0; } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USmzn.rft
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POApplying Dijkstra's algorithm on a graph of five nodes
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POApplying Dijkstra's algorithm on a graph of five nodes
      1. USGMasucci
      1. VTFavorite
    1. CO`I wish you can help to make the code produce the correct result, Thanks in advance.` How much for an hour? [so] is *not* a collaborative debugging service.
      singulars
      1. POApplying Dijkstra's algorithm on a graph of five nodes
      1. USBartek Banachewicz
    2. COIn this case, a debugger can help you better than anyone here.
      singulars
      1. POApplying Dijkstra's algorithm on a graph of five nodes
      1. USHAL
    3. CO@Bartek , i am going to remove that phrase, i think that there maybe some people like to take a look at somebody else code , nobody needs be obligated to improve this code , it is just about sharing something with others, thank you for editing the question.
      singulars
      1. POApplying Dijkstra's algorithm on a graph of five nodes
      1. USmzn.rft
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload