ベルマンフォード法とダイカストラ法について

メモ。
AOJのこの問題で、入力数が大きいパターンでタイムアウトになっていた。

有向グラフが与えられる。このとき、頂点rから各頂点までの最短経路を求めよ。

単一始点最短経路 | グラフ | Aizu Online Judge

ダイカストラではなくベルマンフォードで解いていたのが原因。この問題では、Vが最大100000、Eが最大500000と大きいので、O(VE)であるベルマンフォードだと制限時間内(3s)に処理が終わらない。 追記：ベルマンフォードを適切に実装したら問題なかったようだ。コードも差し替えておく。
ダイカストラ： O(E logV)
ベルマンフォード： O(VE)

教訓：負の辺がない場合はダイカストラの利用を考える

• ベルマンフォードでの解答（抜粋）

/// <summary>
/// find the shortest path from start to all destination
/// </summary>
public class BellmanFord
{
    public List<edge> Edge = new List<edge>();
    public int V;   // number of vertex

    public class edge
    {
        public int from, to, cost;
        public edge(int _from, int _to, int _cost)
        {
            from = _from;
            to = _to;
            cost = _cost;
        }
    }

    public BellmanFord(int v)
    {
        V = v;
    }

    /// <summary>
    ///  return shortestPath[V] represents distance from startIndex
    /// </summary>
    public int[] GetShortestPath(int startIndex)
    {
        int[] shortestPath = new int[V];
        var INF = Int32.MaxValue;

        for (int i = 0; i < V; i++) shortestPath[i] = INF;
        shortestPath[startIndex] = 0;
        while (true)
        {
            bool update = false;
            foreach (edge e in Edge)
            {
                if (shortestPath[e.from] != INF && shortestPath[e.to] > shortestPath[e.from] + e.cost)
                {
                    shortestPath[e.to] = shortestPath[e.from] + e.cost;
                    update = true;
                }
            }
            if (!update) break;
        }

        return shortestPath;
    }

    /// <summary>
    ///  return true if it has negative close loop
    /// </summary>
    public bool HasNegativeLoop()
    {
        int[] d = new int[V];
        for (int i = 0; i < V; i++)
        {
            foreach (edge e in Edge)
            {
                if (d[e.to] > d[e.from] + e.cost)
                {
                    d[e.to] = d[e.from] + e.cost;
                    if (i == V - 1) return true;
                }
            }
        }
        return false;
    }
}

• ダイカストラでの解答（抜粋）

/// <summary>
/// Get min cost between two points
/// </summary>
public class Dijkstra
{
    private class Edge
    {
        public int T { get; set; }
        public int C { get; set; }
    }

    private int maxIndex = -1;
    private const int INF = Int32.MaxValue;

    private Dictionary<int, List<Edge>> _edgeArray = new Dictionary<int, List<Edge>>();

    /// <summary>
    /// Dijkstra, get min cost between two points
    /// should not contain negatie cost path
    /// </summary>
    /// <param name="size">max index of vertice</param>
    public Dijkstra(int size)
    {
        maxIndex = size + 1;
    }

    // Add a path with its cost
    public void AddPath(int s, int t, int cost)
    {
        if (!_edgeArray.ContainsKey(s)) _edgeArray.Add(s, new List<Edge>());
        _edgeArray[s].Add(new Edge() { T = t, C = cost });
    }

    //Get the min cost from s
    //return Int32.MaxValue if no path
    public int[] GetMinCost(int s)
    {
        int[] cost = new int[maxIndex];
        for (int i = 0; i < cost.Length; i++) cost[i] = INF;
        cost[s] = 0;

        var priorityQueue = new PriorityQueue<ComparablePair<int, int>>(_edgeArray.Sum( e => e.Value.Count()) + 1);
        priorityQueue.Push(new ComparablePair<int, int>(0, s));

        while (priorityQueue.Count() > 0)
        {
            var costDestinationPair = priorityQueue.Pop();
            if (cost[costDestinationPair.Item2] < costDestinationPair.Item1) continue;
            if (!_edgeArray.ContainsKey(costDestinationPair.Item2)) continue;

            foreach (var edge in _edgeArray[costDestinationPair.Item2])
            {
                var newCostToi = costDestinationPair.Item1 + edge.C;
                if (newCostToi < cost[edge.T])
                {
                    cost[edge.T] = newCostToi;
                    priorityQueue.Push(new ComparablePair<int, int>(newCostToi, edge.T));
                }
            }
        }

        return cost;
    }
}

PriorityQueueを自作する必要があるのと、Dijkstra内を単純な配列にするとメモリが足りなくなるのが面倒だった。
こういう問題だとC++を使ったほうが楽そうだ。