# はじめに

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]

Longest path(最長経路)を求めます。

Bellman–Ford algorithmを使って求めます。

# example

A, B, C, D, Eの作業があります。作業はedgeで表現します。

graphvizを使った図を示します。

sample.dot
```digraph g {
node[shape=point];
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

// create edge / vertex

// 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
```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 です。