Databases
StackOverflow2013
Postsdbo
PODijksta's Algorithm not finding path in Adjacency Matrix
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PODijksta's Algorithm not finding path in Adjacency Matrix
    primarykey
    data
    text
    <p>For some reason when I run dijkstra's algorithm on my randomly generated matrix it does not find paths between all the nodes even though it's clear that it's a connected graph. I've printed out the graphs and they always follow this form</p> <pre><code>0--2--3 | | | 4--5--6 | | | 7--8--9 </code></pre> <p>Right now I'm only working with a 3*3 matrix and am trying to get that to work properly. The below code makes a adjacency matrix with 9 nodes and randomly generates a number between 1 and 3 to represent the weights of edges. I use 4 for infinity. source is hard coded to 0 and numOfVertices 9</p> <pre><code>#include&lt;iostream&gt; #include &lt;time.h&gt; #include &lt;math.h&gt; #define INFINITY 4 #define V 9 using namespace std; class Dijkstra{ private: int predecessor[20],distance[20]; bool mark[20]; int source; int destination; int numOfVertices; char gameMode; public: int adjMatrix[9][9]; void read(); void initialize(); void setSource(int k); int getClosestUnmarkedNode(); void calculateDistance(); void output(); int randomEdge(); int randomNode(); void printPath(int); }; void Dijkstra::read(){ numOfVertices = 4; for(int i = 0; i &lt; numOfVertices;i++){ for(int j = 0; j &lt; numOfVertices;j++){ if(i == j) adjMatrix[i][j] = 0; else if(j &gt;= i){ if(j == i + 1 || j == i - 1 || j == i + sqrt((double)numOfVertices)|| j == i - sqrt((double)numOfVertices)) adjMatrix[i][j] = randomEdge(); else adjMatrix[i][j] = 4; if((i % ((int)sqrt((double)numOfVertices)) == ((int)sqrt((double)numOfVertices)) - 1) &amp;&amp; j == i + 1) adjMatrix[i][j] = 4; } else adjMatrix[i][j] = adjMatrix[j][i]; cout&lt;&lt;adjMatrix[i][j]&lt;&lt; " "; } cout&lt;&lt; "\n"; } source = 0; } void Dijkstra::initialize(){ for(int i=0;i&lt;numOfVertices;i++) { mark[i] = false; predecessor[i] = -1; distance[i] = INFINITY; } distance[source]= 0; } int Dijkstra::getClosestUnmarkedNode(){ int minDistance = INFINITY; int closestUnmarkedNode = 0; for(int i=0;i&lt;numOfVertices;i++) { if((!mark[i]) &amp;&amp; ( minDistance &gt;= distance[i])) { minDistance = distance[i]; closestUnmarkedNode = i; } } return closestUnmarkedNode; } void Dijkstra::calculateDistance(){ initialize(); int minDistance = INFINITY; int closestUnmarkedNode; int count = 0; while(count &lt; numOfVertices) { closestUnmarkedNode = getClosestUnmarkedNode(); mark[closestUnmarkedNode] = true; for(int i=0;i&lt;numOfVertices;i++) { if((!mark[i]) &amp;&amp; (adjMatrix[closestUnmarkedNode][i]&gt;0) ) { if(distance[i] &gt; distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i]) { distance[i] = distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i]; predecessor[i] = closestUnmarkedNode; } } } count++; } } void Dijkstra::printPath(int node){ if(node == source) cout&lt;&lt;node&lt;&lt;".."; else if(predecessor[node] == -1) cout&lt;&lt;"No path from "&lt;&lt;source&lt;&lt;"to "&lt;&lt;node&lt;&lt;endl; else { printPath(predecessor[node]); cout&lt;&lt;node&lt;&lt;".."; } } void Dijkstra::output(){ for(int i=0;i&lt;numOfVertices;i++) { if(i == source) cout&lt;&lt;source&lt;&lt;".."&lt;&lt;source; else printPath(i); cout&lt;&lt;"-&gt;"&lt;&lt;distance[i]&lt;&lt;endl; } } int Dijkstra::randomEdge(){ return rand() % 3 + 1; } void Dijkstra::setSource(int k){ source = k; } int main(int argc, char** argv){ Dijkstra G; G.read(); G.calculateDistance(); G.output(); int k; cin&gt;&gt; k; exit(0); } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USAnthony Porter
    1. USAnthony Porter
    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. PODijksta's Algorithm not finding path in Adjacency Matrix
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PODijksta's Algorithm not finding path in Adjacency Matrix
      1. USAnthony Porter
      1. VTFavorite
    1. COCould you post a [minimal complete example](http://sscce.org)?
      singulars
      1. PODijksta's Algorithm not finding path in Adjacency Matrix
      1. USBeta
    2. CO@Beta is the best way to post this minimal example to just edit my post and dd it on? or is there some other way
      singulars
      1. PODijksta's Algorithm not finding path in Adjacency Matrix
      1. USAnthony Porter
    3. COEditing your post is the correct way.
      singulars
      1. PODijksta's Algorithm not finding path in Adjacency Matrix
      1. USBeta
 

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