ダイクストラ法の実装(C#)

前エントリでPriorityQueueが用意できたので、最短経路を解くコードをダイクストラで書いてみた。PriorityQueueを二分ヒープで実装したため、計算コストはO((E+V)logV)になっているはず。

ダイクストラ法 - Wikipedia

なお、C#のTupleがIComparableではないので、簡単なPairクラスも作成している。

    /// <summary>
    /// Get min cost between two points
    /// </summary>
    public class Dijkstra
    {
        private int maxIndex = -1;
        private const int INF = Int32.MaxValue;

        private int[,] _edgeArray;

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

            for (int i = 0; i < _edgeArray.GetLength(0); i++)
            {
                for (int j = 0; j < _edgeArray.GetLength(1); j++)
                {
                    _edgeArray[i, j] = INF;
                    if (i == j) _edgeArray[i, j] = 0;
                }
            }
        }

        // Add a path(no direction) with its cost
        public void AddPath(int s, int t, int cost)
        {
            _edgeArray[s, t] = Math.Min(_edgeArray[s, t], cost);
            _edgeArray[t, s] = _edgeArray[s, t];
        }

        //Get the min cost between s and t
        //return Int32.MaxValue if no path
        public int GetMinCost(int s, int t)
        {
            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>>(maxIndex);
            priorityQueue.Push( new ComparablePair<int, int>(0, s) );

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

                for (int i = 0; i < maxIndex; i++)
                {
                    int newCostToi = _edgeArray[costDestinationPair.Item2, i] == INF ? INF :
                        costDestinationPair.Item1 + _edgeArray[costDestinationPair.Item2, i];
                    if (newCostToi < cost[i])
                    {
                        cost[i] = newCostToi;
                        priorityQueue.Push(new ComparablePair<int, int>(newCostToi, i));
                    }
                }
            }

            return cost[t];
        }
    }

    public class ComparablePair<T, U> : IComparable where T : IComparable<T>
    {
        public readonly T Item1;
        public readonly U Item2;

        public int CompareTo(object obj)
        {
            ComparablePair<T, U> castedObj = (ComparablePair<T, U>)obj;
            return this.Item1.CompareTo(castedObj.Item1);
        }

        public ComparablePair(T t, U u)
        {
            Item1 = t;
            Item2 = u;
        }
    }