title: Shortest Path Algorithm C++ Dijkstra's With Layover Included
body: <p>Good morning everyone,</p>
  
  <p>I have a problem where I have to calculate the shortest path (including layovers) from one train station to another.  I usually don't ask for help but I am very stuck on this one. I started out by writing a standard dijkstra's algorithm and thought I could modify it for the layovers but that hasn't been the case. The program is set up as an adjacency matrix of [stationCount][stationCount] size made of edge structures. Each edge structure has an:</p>
  
  <pre><code>int departure; int arrival; int totalTime; (arrival - departure)
  </code></pre>
  
  <p>and all of the times are in military time (0900, 1230, etc.). The method I am having issues with is posted below and I am fairly certain my issues are with calculating/adding in the layovers. I have commented that section to mark it.</p>
  
  <p>Lastly, this is the input data I am with:</p>
  
  <pre><code>1 2 0430 0600
  1 4 0550 1000 
  2 4 0630 1100 
  2 5 1130 1300 
  3 1 1245 1500 
  3 6 0300 0530 
  4 5 0730 0945 
  4 7 1145 1600 
  4 6 1500 1900 
  4 3 1000 1330 
  5 7 1430 1730 
  7 6 1550 1800
  </code></pre>
  
  <p>I have asked the program to try to return the shortest path from (1, 6) but it is not returning the valid path. The shortest path as I have calculated it would be 1->4 (0450) + (0500) -layover + 4->6 (0400) = (1350) which I could then convert to 13 hours 10 minutes. There are multiple other paths it could take but all of them start earlier and end at the same time or later making them longer paths.  If anyone has any guidance on what I am doing wrong or of a better way to do this please let me know.  Thank you.</p>
  
  <pre><code>int TRAINS::dijkstra(int source, int destination)
  {
      vector &lt;bool&gt; vertexSet;
      int distance[stationCount];
      int minNode, minDistance, source, destination, count = 0, previousNode;
  
      for(int i = 1; i &lt; stationCount; ++i)
      {
          distance[i] = INFINITY;
          vertexSet.push_back(false);
      }
  
      distance[source] = 0;
      while((!empty(vertexSet)) &amp;&amp; count &lt; stationCount - 1)
      {
          count++;
          minNode = INFINITY;
          minDistance = INFINITY;
  
          for(int vertex = 1; vertex &lt; stationCount; ++vertex)
          {
              if(vertexSet[vertex] == false &amp;&amp; distance[vertex] &lt;= minDistance)
              {
                  minDistance = distance[vertex];
                  minNode = vertex;
              }
          }
  
          vertexSet[minNode] = true;
  
          //so what i tried to do is that if it is the first time running through (i.e. source == minNode then it will set the distance for all verteces to .totalTime (the regular weight) and that seems to work
          for(int vertex = 1; vertex &lt; stationCount; ++vertex)
          {
              if(vertexSet[vertex] == false &amp;&amp; matrix[minNode][vertex].arrival &gt; 0)
              {
                  if(minNode == source)
                  {
                      if(distance[minNode] != INFINITY &amp;&amp; matrix[minNode][vertex].totalTime &lt; distance[vertex])
                      {
                          distance[vertex] = matrix[minNode][vertex].totalTime;
  
                          if(vertex == destination)
                          {
                              return distance[vertex];
                          }
                      }
                  }
  
                  //then here if it wasn't the first time (this is where I am having trouble... i was trying to have it take the current departure time - the previous arrival time to calculate the layover and then add it to the current distance (distance[minNode]) plush the actual weight still... but somewhere this is going wrong and i am not getting the right output.
                  else
                  {
                      if(distance[minNode] != INFINITY &amp;&amp; matrix[minNode][vertex].departure &gt; 0 &amp;&amp; matrix[minNode][vertex].departure - matrix[previousNode][minNode].arrival + matrix[minNode][vertex].totalTime + distance[minNode] &lt; distance[vertex])
                      {
                          distance[vertex] = matrix[minNode][vertex].departure - matrix[previousNode][minNode].arrival + matrix[minNode][vertex].totalTime + distance[minNode];
                      }
                      if(vertex == destination)
                      {
                          return distance[vertex];
                      }
                  }
              }
          }
          //before the next cycle i set the current minNode to previous for use in the next cycle
          previousNode = minNode;
      }
      return -1;
  
  }
  
  -
  </code></pre>