pgm16_16.txt

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

//
//   This file contains the C# code from Program 16.16 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_16.txt
//
public class Algorithms
{
    public static Digraph FloydsAlgorithm(Digraph g)
    {
	int n = g.NumberOfVertices;
	int[,] distance = new int[n, n];
	for (int v = 0; v < n; ++v)
	    for (int w = 0; w < n; ++w)
		distance[v, w] = int.MaxValue;

	foreach (Edge e in g.Edges)
	{
	    distance[e.V0.Number, e.V1.Number] = (int)e.Weight;
	}

	for (int i = 0; i < n; ++i)
	    for (int v = 0; v < n; ++v)
		for (int w = 0; w < n; ++w)
		    if (distance[v, i] != int.MaxValue &&
			distance[i, w] != int.MaxValue)
		    {
			int d = distance[v, i] + distance[i, w];
			if (distance[v, w] > d)
			    distance[v, w] = d;
		    }

	Digraph result = new DigraphAsMatrix(n);
	for (int v = 0; v < n; ++v)
	    result.AddVertex(v);
	for (int v = 0; v < n; ++v)
	    for (int w = 0; w < n; ++w)
		if (distance[v, w] != int.MaxValue)
		    result.AddEdge(v, w, distance[v, w]);
	return result;
    }
}