grdijk1.c

来自「经典c++程序的实现」· C语言 代码 · 共 29 行

void Dijkstra(Graph& G, int s) {  // Compute shortest path distances
  //int D[G.n()];
  int *D;
  D = new int [G.n()];
  for (int i=0; i<G.n(); i++)     // Initialize
    D[i] = INFINITY;
  D[s] = 0;
  for (i=0; i<G.n(); i++) {       // Process the vertices
    int v = minVertex(G, D);
    G.Mark[v] = VISITED;
    if (D[v] == INFINITY) return; // Remaining vertices unreachable
    for (Edge w = G.first(v); G.isEdge(w); w = G.next(w))
      if (D[G.v2(w)] > (D[v] + G.weight(w)))
        D[G.v2(w)] = D[v] + G.weight(w);
	for (int j=0; j<G.n(); j++)     // Initialize
      cout << D[j] << "  ";
	cout << endl;
  }
}

int minVertex(Graph& G, int* D) { // Find min cost vertex
  int v;  // Initialize v to any unvisited vertex;
  for (int i=0; i<G.n(); i++)
    if (G.Mark[i] == UNVISITED) { v = i; break; }
  for (i=0; i<G.n(); i++)  // Now find smallest value
    if ((G.Mark[i] == UNVISITED) && (D[i] < D[v])) v = i;
  return v;
}