Аналогичен поиску кратчайших путей за разницей знаков при релаксации ребра.
|
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 AcyclicLP { private double[] distTo; private DirectedEdge[] edgeTo; public AcyclicLP(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.NegativeInfinity; 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.NegativeInfinity; } 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; } } } |