title: Dijkstras algorithm in c#
body: <p>Building a chart control that uses Dijkstras alg from scratch.  I have scoured the internet trying to understand this algorithm.  I think I finally understand it, but my code is failing to work properly.  Hoping someone might be able to take a peek at this and see if they might know what the deal with it is...</p>
  
  <p>I will paste in three methods as I think that is everything that might be needed.</p>
  
  <p>For starters, I will say that I created my own Vertex datatype.  It contains the ID of the node, the X and Y, a status string, and a parent which is also of vertex datatype, and distance of integer.</p>
  
  <pre><code>    //function to populate lists with all the vertices on the graph
      private List&lt;Vertex&gt; getNodes()
      {
          myVertices.Clear();
          //get all non-dg nodes in list
          for (int i = 0; i &lt; chtGraph.Series[0].Points.Count; i++)
          {
              Vertex vertice = new Vertex(chtGraph.Series[0].Points[i]["ID"], (float)chtGraph.Series[0].Points[i].XValue, (float)chtGraph.Series[0].Points[i].YValues[0], "UNVISITED", Convert.ToInt32(chtGraph.Series[0].Points[i].Label), double.PositiveInfinity, null);
              myVertices.Insert(i, vertice);
          }
  
          //get all dg nodes in list
          for (int i = 0; i &lt; chtGraph.Series[1].Points.Count; i++)
          {
              Vertex vertice = new Vertex(chtGraph.Series[1].Points[i]["ID"], (float)chtGraph.Series[1].Points[i].XValue, (float)chtGraph.Series[1].Points[i].YValues[0], "UNVISITED", Convert.ToInt32(chtGraph.Series[1].Points[i].Label), double.PositiveInfinity, null);
              myVertices.Insert(i, vertice);
          }
          return myVertices;
      }
  
      //function to return to a list all the adjacents for a specified node.  Excludes parent node
      private List&lt;Vertex&gt; checkAdjacents(Vertex node, int intTransPower)
      {
          List&lt;Vertex&gt; Adjacents = new List&lt;Vertex&gt;();
          int distance;
  
          for (int i = 0; i &lt; myVertices.Count; i++)
          {
              if (node.id != myVertices[i].id)
              {
                  distance = calcDistance(node.x, node.y, myVertices[i].x, myVertices[i].y);
  
                  if (distance &lt;= intTransPower)
                  {
                      if (rdbTotalLength.Checked)
                      {
                          myVertices[i].distance = distance;
                      }
                      else if (rdbPathEnergy.Checked)
                      {
                          myVertices[i].distance = getCost(node, myVertices[i]);
                      }
                      else
                      {
                          myVertices[i].distance = 1;
                      }
  
                      myVertices[i].parent = node;
                      Adjacents.Add(myVertices[i]);
  
                      foreach (Vertex p in openList)
                      {
                          if (myVertices[i].id == p.id)
                          {
                              p.distance = myVertices[i].distance;
                              p.parent = myVertices[i].parent;
                          }
                      }
                  }
              }
          }
  
          return Adjacents;
  
      }
  </code></pre>
  
  <p>And here is dijkstras.... currently isn't working properly and I just can't figure it out.</p>
  
  <pre><code>private void dijkstra(Vertex start, Vertex end)
      {
  
          openList.Clear();
  
          //populate two lists with all the nodes in the graph
          openList = getNodes();
          myVertices = getNodes();
  
          //adjacents list for each vertex visited
          List&lt;Vertex&gt; adjacents = new List&lt;Vertex&gt;();
  
          //final list that is populated with the final path of vertices
          List&lt;Edge&gt; shortestPath = new List&lt;Edge&gt;();
  
          //used in calculating adjacent nodes.  If distance is greater than transpower, then nodes are not connected
          int intTransPower = Convert.ToInt32(txtTransPower.Text);
  
          //set current vertex as the starting node
          Vertex current = start;
  
          //set initially to false
          bool pathFound = false;
  
          //find the starting node from the list of all vertices.  Set it's distance to 0
          foreach (Vertex p in openList)
          {
              if (p.id == current.id)
              {
                  p.status = current.status;
                  p.distance = 0;
              }
          }
          foreach (Vertex p in myVertices)
          {
              if (p.id == current.id)
              {
                  p.status = current.status;
                  p.distance = 0;
              }
          }
  
          //reorder the list to bring the starting node to the first element
          openList = openList.OrderBy(h =&gt; h.distance).ToList();
  
          //openList.Add(current);
          //this.insert(openList, current, true);
  
          // Repeat while the openlist is not empty and you haven't reached the end
          while (openList.Count &gt; 0)
          {
              //remove node at element 0.  Sorted by smallest distance so it always gets removed first
              current = openList[0];
              openList.RemoveAt(0);
  
              //if the current node = the ending node, then we have found the path.  Break loop and build the final path.
              if (current.id == end.id)
              {
                  pathFound = true;
                  break;
              }
  
              //collect up all the adjacent nodes for the current vertex
              //does NOT include the current vertex we are on
              adjacents = checkAdjacents(current, intTransPower);
  
              foreach (Vertex v in adjacents)
              {
                  float alt =  (float)current.distance + calcDistance(current.x, current.y, v.x, v.y);
                  Convert.ToInt32(alt);
  
                  if (alt &lt; v.distance)
                  {
                      v.distance = alt;
                      v.parent = current;
                      for (int i = 0; i &lt; openList.Count; i++)
                      {
                          if (v.id == openList[i].id)
                          {
                              openList[i].distance = alt;
                              openList[i].parent = current;
                          }
                      }
                  }
  
              }
              openList = openList.OrderBy(h =&gt; h.distance).ToList();
          }
  
          if (pathFound)
          {
              // collect path
              this.foundPath.Clear();
              Vertex last = current;
              while (current != start &amp;&amp; current != null)
              {
                  this.foundPath.Add(current);
                  if (current.parent == last)
                      break;
                  last = current;
                  current = current.parent;
              }
              this.foundPath.Add(current);
          }
  
      }
  </code></pre>