pgm16_14.cpp

此文件为网络书籍数据结构的面向对象方法的源码

//
//   This file contains the C++ code from Program 16.14 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm16_14.cpp
//
Digraph& DijkstrasAlgorithm (Digraph const& g, Vertex const& s)
{
    unsigned int const n = g.NumberOfVertices ();
    Array<TableEntry> table (n);
    PriorityQueue& queue = *new BinaryHeap (g.NumberOfEdges ());
    table [s].distance = 0;
    queue.Enqueue (*new Assoc (0, const_cast<Vertex&> (s)));
    while (!queue.IsEmpty ())
    {
	Assoc& assoc =
	    dynamic_cast<Assoc&> (queue.DequeueMin ());
	Vertex& v0 = dynamic_cast<Vertex&> (assoc.Value ());
	if (!table [v0].known)
	{
	    table [v0].known = true;
	    Iterator& p = g.EmanatingEdges (v0);
	    while (!p.IsDone ()) {
		WeightedEdge& edge =
		    dynamic_cast<WeightedEdge&> (*p);
		Vertex& v1 = edge.V1 ();
		Int& weight =
		    dynamic_cast<Int&> (edge.Weight ());
		int const d = table [v0].distance + weight;
		if (table [v1].distance > d)
		{
		    table [v1].distance = d;
		    table [v1].predecessor = v0;
		    queue.Enqueue (*new Assoc (d, v1));
		}
		++p;
	    }
	    delete &p;
	}
	delete &assoc;
    }
    delete &queue;

    Digraph& result = *new DigraphAsLists (n);
    for (Vertex::Number v = 0; v < n; ++v)
	result.AddVertex (*new WeightedVertex (
	    v, *new Int (table [v].distance)));
    for (Vertex::Number v = 0; v < n; ++v)
	if (v != s)
	    result.AddEdge (*new Edge (
		result [v], result [table [v].predecessor]));
    return result;
}