/*******************************************************************************
+
+  LEDA 3.5
+
+  dijkstra.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/


//------------------------------------------------------------------------------
// DIJKSTRA  (single source shortest paths)
//
// S. N"aher (last modification: 1996)
//------------------------------------------------------------------------------


#include <LEDA/graph_alg.h>
#include <LEDA/node_pq.h>


void DIJKSTRA(const graph& G, node s, const edge_array<num_type>& cost,
                                            node_array<num_type>& dist,
                                            node_array<edge>& pred)
{ /*
     computes single source shortest paths from node s for
     a non-negative network (G,cost), computes for all nodes v:
     a) dist[v] = cost of shortest path from s to v
     b) pred[v] = predecessor edge of v in shortest paths tree
  */

  node_pq<num_type>  PQ(G);
  node v;
  edge e;

  forall_nodes(v,G)
  { pred[v] = nil;
    dist[v] = max_num;
   }

  dist[s] = 0;
  PQ.insert(s,0);

  while (! PQ.empty())
  { node u = PQ.del_min();
    num_type du = dist[u];
    forall_adj_edges(e,u)
    { v = G.opposite(u,e);
      num_type c = du + cost[e];
      if (c < dist[v])
      { if (dist[v] == max_num)
           PQ.insert(v,c);
        else
           PQ.decrease_p(v,c);
        dist[v] = c;
        pred[v] = e;
       }
     }
   }
}



void DIJKSTRA(const graph& G, node s, const edge_array<num_type>& cost,
                                            node_array<num_type>& dist)
{ /*
     computes single source shortest paths from node s for
     a non-negative network (G,cost), computes for all nodes v
     dist[v] = cost of shortest path from s to v
  */

  node_pq<num_type>  PQ(G);
  node v;
  edge e;

  forall_nodes(v,G) dist[v] = max_num;

  dist[s] = 0;
  PQ.insert(s,0);

  while (! PQ.empty())
  { node u = PQ.del_min();
    num_type du = dist[u];
    forall_adj_edges(e,u)
    { v = G.opposite(u,e);
      num_type c = du + cost[e];
      if (c < dist[v])
      { if (dist[v] == max_num)
           PQ.insert(v,c);
        else
           PQ.decrease_p(v,c);
        dist[v] = c;
       }
     }
   }
}


