grdijk2.c

经典c++程序的实现

void Dijkstra(Graph& G, int s) {  // Priority queue version
  int v;                          // The current vertex
  //int Dist[G.n()];                   // Distance array
  //int* E[G.e()];                  // Heap array with lots of space
  int *Dist, *E;
  Dist = new int [G.n()];
  E = new int [G.e()];
  //E[0] = &Dist[s];                  // Initialize heap array
  E[0] = (&Dist[s])[0];
  //heap H(E, 1, G.e());            // Create the heap
  heap H(&E, 1, G.e());
  for (int i=0; i<G.n(); i++)     // Initialize distance array
    Dist[i] = INFINITY;
  Dist[s] = 0;
  for (i=0; i<G.n(); i++) {       // Now, get distances
    do { v = H.removemin() - Dist; } // Get position in D
      while (G.Mark[v] == VISITED);
    G.Mark[v] = VISITED;
    if (Dist[v] == INFINITY) return; // Remaining vertices unreachable
    for (Edge w = G.first(v); G.isEdge(w); w = G.next(w))
      if (Dist[G.v2(w)] > (Dist[v] + G.weight(w))) { // Update D
        Dist[G.v2(w)] = Dist[v] + G.weight(w);
        H.insert(&Dist[G.v2(w)]);    // Insert new distance in heap
      }
  }
}