using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using U.Graph;
using U.ListOperations;

namespace Algorithms.Nw.ShortestPathAllPairs
{
    public class FloydWarshall : ShortestPathAllPairsAlgorithm
    {
        public override void run(Graph graph, bool keepTime)
        {
            if (keepTime) { base.startTimer(); }
            int N = graph.getNbNodes();
            int A = graph.getNbArcs();
            base.D = UArray.sameValues<double>(double.MaxValue, N, N);
            base.P = UArray.sameValues<int>(-1, N, N);
            for (int i = 0; i < N; i++) { D[i, i] = 0; }
            for (int a = 0; a < A; a++)
            {
                Arc arc = graph.getArc(a);
                int i = arc.getFromIndex();
                int j = arc.getToIndex();
                D[i, j] = arc.getCost();
                P[i, j] = i;
            }
            for (int k = 0; k < N; k++)
            {
                for (int i = 0; i < N; i++)
                {
                    for (int j = 0; j < N; j++)
                    {
                        if (D[i, j] > D[i, k] + D[k, j])
                        {
                            D[i, j] = D[i, k] + D[k, j];
                            P[i, j] = k;
                        }
                    }
                }
            }
            if (keepTime) { base.stopTimer(); }
        }
    }
}
