Класс
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace WOrGraph { class AcyclicSP { private double[] distTo; private DirectedEdge[] edgeTo; public AcyclicSP(EdgeWeightedDigraph G, int s) { distTo = new double[G.GetVertices()]; edgeTo = new DirectedEdge[G.GetVertices()]; for (int v = 0; v < G.GetVertices(); v++) distTo[v] = Double.PositiveInfinity; distTo[s] = 0.0; ValidateVertex(s); Topological topological = new Topological(G); if (!topological.IsOrder()) throw new ArgumentException("Digraph is not acyclic."); foreach (int v in topological.ReversePost) { foreach (DirectedEdge e in G.GetAdj(v)) Relax(e); } } // relax edge e private void Relax(DirectedEdge e) { int v = e.From(), w = e.To(); if (distTo[w] > distTo[v] + e.GetWeight()) { distTo[w] = distTo[v] + e.GetWeight(); edgeTo[w] = e; } } private void ValidateVertex(int v) { int V = distTo.Length; if (v < 0 || v >= V) throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1)); } public double DistTo(int v) { ValidateVertex(v); return distTo[v]; } public bool IsPathTo(int v) { ValidateVertex(v); return distTo[v] < Double.PositiveInfinity; } public IEnumerable<DirectedEdge> GetPathTo(int v) { ValidateVertex(v); if (!IsPathTo(v)) return null; Stack<DirectedEdge> path = new Stack<DirectedEdge>(); for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.From()]) { path.Push(e); } return path; } } } |
Проверка на графе
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
8 13 5 4 0,35 4 7 0,37 5 7 0,28 5 1 0,32 4 0 0,38 0 2 0,26 3 7 0,39 1 3 0,29 7 2 0,34 6 2 0,40 3 6 0,52 6 0 0,58 6 4 0,93 |
Пример использования в консоли
|
1 2 3 4 5 6 7 8 9 10 11 |
// AcyclicSP Console.WriteLine("Acyclic ASP"); AcyclicSP asp = new AcyclicSP(G2,5); int v = 2; if (asp.IsPathTo(v)) { Console.WriteLine("path from 5 to "+v); Queue<DirectedEdge> path = new Queue<DirectedEdge>(asp.GetPathTo(v)); foreach (DirectedEdge e in path) Console.WriteLine(e.From() + " -> " + e.To()); } else Console.WriteLine("no path from 5 to "+v); |
