Databases
StackOverflow2013
Postsdbo
PO
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    text
    copied!<p>As far as I understand your code, it lacks a few essential parts of Dijkstra's algorithm. Look at <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="nofollow">dijkstra on wikipedia</a> to see all steps of the algorithm. Two things I can't find in your algorithm but that are definitely part of Dijkstra's algorithm:</p> <ol> <li>Assigning an infinite (very high) initial distance (in your case carried) to every vertex</li> <li>The total distance to every newly reached vertex is the weight/length of the edge leading to it + the distance of the other vertex to the source</li> </ol> <p>I will include a working Dijkstra algorithm, so you have something to compare your own algorithm with. It includes some more advanced data structures (e.g. priority queue) but you will encounter that sooner or later anyway. Good luck learning and correcting!</p> <pre><code>#define MAX_VER 1000 // Maximum number of vertices #define INFINITE 0x3fffffff // 7*f ~ 1.000.000.000 #include &lt;vector&gt; #include &lt;queue&gt; #include &lt;iostream&gt; using namespace std; struct edge { int to; int length; edge(int to, int length) : to(to), length(length) {} }; struct vertex { vector&lt;edge&gt; edges; int dis; int prev; }; vertex vertices[MAX_VER]; void reset() { for (int i=0; i &lt; MAX_VER; i++) { vertices[i].edges.clear(); vertices[i].dis = INFINITE; vertices[i].prev = -1; } } void addedge(int from, int to, int length=-1, bool directed=true) { vertices[from].edges.push_back(edge(to, length)); if (!directed) vertices[to].edges.push_back(edge(from, length)); } typedef pair&lt;int, int&gt; pp; void dijkstra(int source) { //distance, vertex priority_queue&lt;pp, vector&lt;pp&gt;, greater&lt;pp&gt; &gt; q; vertices[source].dis = 0; q.push(make_pair(0, source)); while (!q.empty()) { int u = q.top().second; int dis = q.top().first; q.pop(); if (dis &gt; vertices[u].dis) continue; for (size_t i = 0; i &lt; vertices[u].edges.size(); i++) { edge &amp;e = vertices[u].edges[i]; if (dis + e.length &lt; vertices[e.to].dis) { vertices[e.to].dis = dis + e.length; vertices[e.to].prev = u; q.push(make_pair(vertices[e.to].dis, e.to)); } } } } int main() { reset(); addedge(0, 1, 5, false); addedge(0, 2, 9, false); addedge(0, 3, 4, false); addedge(0, 4, 6, false); addedge(1, 2, 2, false); addedge(1, 3, 5, false); addedge(1, 4, 7, false); addedge(2, 3, 1, false); addedge(2, 4, 8, false); addedge(3, 4, 3, false); dijkstra(2); cout &lt;&lt; "Distance from vertex 2 to 4 is: " &lt;&lt; vertices[4].dis &lt;&lt; endl; return 0; } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

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