Позволяет работать с отрицательными весами.
Класс BellmanFordSP
В конструкторе строит дерево кратчайших путей для всех вершин, до которых можно дотянуться. Если на пути отрицательный цикл, итерация переходит на следующую.
|
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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace WOrGraph { class BellmanFordSP { private double[] distTo; // distTo[v] = distance of shortest s->v path private DirectedEdge[] edgeTo; // edgeTo[v] = last edge on shortest s->v path private bool[] onQueue; // onQueue[v] = is v currently on the queue? private Queue<int> queue; // queue of vertices to relax private int cost; // number of calls to relax() private IEnumerable<DirectedEdge> cycle; // negative cycle (or null if no such cycle) // by finding a cycle in predecessor graph public BellmanFordSP(EdgeWeightedDigraph G, int s) { distTo = new double[G.GetVertices()]; edgeTo = new DirectedEdge[G.GetVertices()]; onQueue = new bool[G.GetVertices()]; for (int v = 0; v < G.GetVertices(); v++) distTo[v] = Double.PositiveInfinity; distTo[s] = 0.0; // Bellman-Ford algorithm queue = new Queue<int>(); queue.Enqueue(s); onQueue[s] = true; while (queue.Count!=0 && !IsNegativeCycle()) { int v = queue.Dequeue(); onQueue[v] = false; Relax(G, v); } } // relax vertex v and put other endpoints on queue if changed private void Relax(EdgeWeightedDigraph G, int v) { //for (DirectedEdge e : G.adj(v)) foreach (DirectedEdge e in G.GetAdj(v)) { int w = e.To(); if (distTo[w] > distTo[v] + e.GetWeight()) { distTo[w] = distTo[v] + e.GetWeight(); edgeTo[w] = e; if (!onQueue[w]) { queue.Enqueue(w); onQueue[w] = true; } } if (cost++ % G.GetVertices() == 0) { FindNegativeCycle(); if (IsNegativeCycle()) return; // found a negative cycle } } } public bool IsNegativeCycle() { return cycle != null; } public IEnumerable<DirectedEdge> GetNegativeCycle() { return cycle; } private void FindNegativeCycle() { int V = edgeTo.Length; EdgeWeightedDigraph spt = new EdgeWeightedDigraph(V); for (int v = 0; v < V; v++) if (edgeTo[v] != null) spt.AddEdge(edgeTo[v]); EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(spt); cycle = finder.GetCycle(); } public double DistTo(int v) { ValidateVertex(v); if (IsNegativeCycle()) throw new ArgumentException("Negative cost cycle exists"); return distTo[v]; } public bool IsPathTo(int v) { ValidateVertex(v); return distTo[v] < Double.PositiveInfinity; } public IEnumerable<DirectedEdge> PathTo(int v) { ValidateVertex(v); if (IsNegativeCycle()) throw new ArgumentException("Negative cost cycle exists"); 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; } 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)); } } } |
Тестовый клиент
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// BellmanFord EdgeWeightedDigraph G3 = new EdgeWeightedDigraph("tinyEWDn.txt"); BellmanFordSP b = new BellmanFordSP(G3, 0); if (!b.IsNegativeCycle()) { Queue<DirectedEdge> q = new Queue<DirectedEdge>(b.PathTo(7)); foreach (DirectedEdge e in q) { Console.WriteLine(e.From() + " - > " + e.To()); } } else { Console.WriteLine("There is negative cycle"); Queue<DirectedEdge> q = new Queue<DirectedEdge>(b.GetNegativeCycle()); foreach (DirectedEdge e in q) { Console.WriteLine(e.From() + " - > " + e.To()); } } |
Граф с отрицательными циклами
Текстовое представление
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
8 15 4 5 0,35 5 4 -0,66 4 7 0,37 5 7 0,28 7 5 0,28 5 1 0,32 0 4 0,38 0 2 0,26 7 3 0,39 1 3 0,29 2 7 0,34 6 2 0,40 3 6 0,52 6 0 0,58 6 4 0,93 |