title: Can Dijkstra's Single Source Shortest Path Algorithm detect an infinite cycle in a graph?
body: <p>So I came to this beautiful problem that asks you to write a program that finds whether a negative infinity shortest path exists in a directed graph. (Also can be thought of as finding whether a "negative cycle" exists in the graph). Here's a link for the problem:</p>
  
  <p><a href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;page=show_problem&amp;problem=499" rel="noreferrer">http://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;page=show_problem&amp;problem=499</a></p>
  
  <p>I successfully solved the problem by running Bellman Ford Algorithm twice by starting with any source in the graph. The second time I run the algorithm, I check if a node can be relaxed. If so, then there is definitely a negative cycle in the graph. Below is my C++ code:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>#include&lt;iostream&gt;
  #include&lt;vector&gt;
  #include&lt;algorithm&gt;
  
  using namespace std;
  
  int main()
  {
      int test;
      cin&gt;&gt;test;
  
      for(int T=0; T&lt;test; T++)
      {
  
          int node, E;
  
          cin&gt;&gt;node&gt;&gt;E; 
  
          int **edge= new int *[E];
          for(int i=0; i&lt;E; i++)
          {
              edge[i]= new int [3];
              cin&gt;&gt;edge[i][0]&gt;&gt;edge[i][1]&gt;&gt;edge[i][2];
          }
  
          int *d= new int [node];
  
          bool possible=false;
  
          for(int i=0; i&lt;node;i++)
          {
              d[i]= 999999999;
          }
  
          d[node-1]=0;
  
          for(int i=0; i&lt;node-1; i++)
          {
  
              for(int j=0; j&lt;E; j++)
              {
                  if(d[edge[j][1]]&gt;d[edge[j][0]]+edge[j][2])
                      d[edge[j][1]]=d[edge[j][0]]+edge[j][2];
              }
          }
  
          // time to judge!
          for(int i=0; i&lt;node-1; i++)
          {
  
              for(int j=0; j&lt;E; j++)
              {
                  if(d[edge[j][1]]&gt;d[edge[j][0]]+edge[j][2])
                  {
                      possible=true;
                      break;
                  }
  
              } 
  
              if(possible)
                  break;
  
          }
  
          if(possible)
              cout&lt;&lt;"possible"&lt;&lt;endl;
          else
              cout&lt;&lt;"not possible"&lt;&lt;endl;
  
      }
  }
  </code></pre>
  
  <p>A professor told me once that Dijkstra's shortest path algorithm cannot find such negative cycle, but he did not justify it. I actually doubt this claim. </p>
  
  <p>My question is, can Dijktstra's single source shortest path algorithm detect that negative cycle?</p>
  
  <p>Of course, I can try Dijkstra's and check whether it will work, but I was excited to share this idea with you.</p>