はじめに

Longest path(最長経路)を求める方法を説明します。
Longest path は Project Management の Critical path(クリティカルパス)のことです。

考え方

Wikipeidaに記載されているとおり、

A longest path between two given vertices s and t in a weighted graph G is the same thing as a shortest path in a graph −G derived from G by changing every weight to its negation. Therefore, if shortest paths can be found in −G, then longest paths can also be found in G.[4]

負の重みを持ったweighted digraph の Shortest path(最短経路)を求めることによって
Longest path(最長経路)を求めます。

負の重みを持ったweighted digraph の Shortest path(最短経路)は
Bellman–Ford algorithmを使って求めます。

example

具体例で説明します。
A, B, C, D, Eの作業があります。作業はedgeで表現します。
点線はダミー作業です。ダミー作業は作業の前後関係を規定します。
graphvizを使った図を示します。

sample.dot

digraph g {
  node[shape=point];
  edge[arrowhead=vee];
  rankdir=LR;

  // define edge
  sa -> ea [label="A"];
  sb -> eb [label="B"];
  sc -> ec [label="C"];
  sd -> ed [label="D"];
  se -> ee [label="E"];

  // dummy edge s:start, f:finish
  s -> sa  [style=dashed]; // start -> A
  s -> sb  [style=dashed]; // start -> B
  ea -> sc [style=dashed]; // A -> C
  eb -> sc [style=dashed]; // B -> C
  eb -> sd [style=dashed]; // B -> D
  ec -> se [style=dashed]; // C -> E
  ed -> se [style=dashed]; // D -> E
  ee -> f  [style=dashed]; // E -> finish
}

console

dot -T png .\sample.dot -o sample.png ; .\sample.png

QuickGraph

C# の Graphライブラリ QuickGraphを使って Longest path / Critical pathを求めます。
QuickGraph は Nugetを使ってInstallできます。
重みを負にしていることに注意してください。

sample.cs

using QuickGraph;
using QuickGraph.Algorithms.Observers;
using QuickGraph.Algorithms.ShortestPath;
using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    class Program
    {
        class Graph : AdjacencyGraph<string, Edge> { }
        class Edge : IEdge<string>
        {
            public Edge(string n, string s, string t, int w)
            {
                Name = n;
                Source = s;
                Target = t;
                Weight = w;
            }
            public string Name { get; set; }
            public string Source { get; set; }
            public string Target { get; set; }
            public int Weight { get; set; }
        }

        static void Main(string[] args)
        {
            Graph g = new Graph();

            // create start / finish vertex
            g.AddVertex("s"); // start
            g.AddVertex("f"); // finish

            // create edge / vertex
            g.AddVertex("sa");
            g.AddVertex("ea");
            g.AddEdge(new Edge("A", "sa", "ea", -6));
            g.AddVertex("sb");
            g.AddVertex("eb");
            g.AddEdge(new Edge("B", "sb", "eb", -5));
            g.AddVertex("sc");
            g.AddVertex("ec");
            g.AddEdge(new Edge("C", "sc", "ec", -8));
            g.AddVertex("sd");
            g.AddVertex("ed");
            g.AddEdge(new Edge("D", "sd", "ed", -2));
            g.AddVertex("se");
            g.AddVertex("ee");
            g.AddEdge(new Edge("E", "se", "ee", -10));

            // create dummy edge
            g.AddEdge(new Edge("d1", "s", "sa", 0)); // start -> A
            g.AddEdge(new Edge("d2", "s", "sb", 0)); // start -> B
            g.AddEdge(new Edge("d3", "ea", "sc", 0)); // A -> C
            g.AddEdge(new Edge("d4", "eb", "sc", 0)); // B -> C
            g.AddEdge(new Edge("d5", "eb", "sd", 0)); // B -> D
            g.AddEdge(new Edge("d6", "ec", "se", 0)); // C -> E
            g.AddEdge(new Edge("d7", "ed", "se", 0)); // D -> E
            g.AddEdge(new Edge("d8", "ee", "f", 0)); // E -> finish

            BellmanFordShortestPathAlgorithm<string, Edge> algo =
                new BellmanFordShortestPathAlgorithm<string, Edge>(g, e => e.Weight);
            VertexPredecessorRecorderObserver<string, Edge> pred =
                new VertexPredecessorRecorderObserver<string, Edge>();
            pred.Attach(algo);
            algo.Compute("s");
            IEnumerable<Edge> path;
            pred.TryGetPath("f", out path);
            int cost = 0;
            foreach (Edge e in path)
            {
                cost += e.Weight;
                Console.WriteLine("Name={0}, weight={1}, cost={2}", e.Name, e.Weight, cost);
            }
            Console.Read();
        }
    }
}

実行結果です。

console

Name=d1, weight=0, cost=0
Name=A, weight=-6, cost=-6
Name=d3, weight=0, cost=-6
Name=C, weight=-8, cost=-14
Name=d6, weight=0, cost=-14
Name=E, weight=-10, cost=-24
Name=d8, weight=0, cost=-24

Longest pathは start -> A -> C -> E -> finish です。
重みの合計は24です。

Longest path / Critical pathを求める

はじめに

考え方

example

QuickGraph

references