pgm16_20.txt

来自「c#版本 算法大全 几乎所有常见的算法 This file contain」· 文本 代码 · 共 40 行

//
//   This file contains the C# code from Program 16.20 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C#"
//   by Bruno R. Preiss.
//
//   Copyright (c) 2001--2002 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.brpreiss.com/books/opus6/programs/pgm16_20.txt
//
public class Algorithms
{
    public static Digraph CriticalPathAnalysis(Digraph g)
    {
	int n = g.NumberOfVertices;

	int[] earliestTime = new int[n];
	earliestTime[0] = 0;
	g.TopologicalOrderTraversal(
	    new EarliestTimeVisitor(earliestTime));

	int[] latestTime = new int[n];
	latestTime[n - 1] = earliestTime[n - 1];
	g.DepthFirstTraversal(new PostOrder(
	    new LatestTimeVisitor(latestTime)), 0);

	Digraph slackGraph = new DigraphAsLists(n);
	for (int v = 0; v < n; ++v)
	    slackGraph.AddVertex(v);
	foreach (Edge e in g.Edges)
	{
	    int slack = latestTime[e.V1.Number]
		- earliestTime[e.V0.Number] - (int)e.Weight;
	    slackGraph.AddEdge(e.V0.Number, e.V1.Number,
		(int)e.Weight);
	}
	return DijkstrasAlgorithm(slackGraph, 0);
    }
}