소개

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 , 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
}

콘솔

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

QuickGraph

C#의 Graph 라이브러리 QuickGraph를 사용하여 Longest path/Critical path를 구합니다.
QuickGraph는 Nuget을 사용하여 설치할 수 있습니다.
가중치가 음수임을 유의하십시오.

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();
        }
    }
}

실행 결과입니다.

콘솔

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입니다.

references

htps // 엔.ぃきぺぢ아. 오 rg / uuki / uenge st_pa th_p 로b ぇm

htps // 엔.ぃきぺぢ아. 오 rg / 우키 / 벳 l 만 % 에 2 % 80 % 93 후 rd_ 아 l 고리 thm