using System;
using System.Collections.Generic;
using System.Text;

//交通分配算法
//fhcfan@163.com,QQ:445194766
    class TripAssignment
    {
        //******************************************************************************************************
        //求兩個點之間的最短距離
        public static void TwoNodesShortestPath
            (
            int startNode,            //IN,起始節(jié)點
            int endNode,              //IN,終止節(jié)點
            double[,] weight,         //IN,各節(jié)點之間的路權
            out double shortestLength,//OUT,兩節(jié)點之間的最短路長
            out string shortestPath   //OUT,兩節(jié)點之間的最短路徑
            )
        {
            int dimensions=weight .GetLength (0);
            double [] L=new double [dimensions ];
            int [] p=new int [dimensions ];
            Dijkstra (startNode ,weight ,L,p);
            shortestLength =L[endNode ];
            shortestPath =(endNode+1) .ToString ();
            int flag = endNode;
            while (p[flag] != -1)
            {
                shortestPath  = (p[flag] + 1)+"->" + shortestPath ;
                flag = p[flag];
            }
        }
        //******************************************************************************************************


        //*****************************************************************************************************
        //求一個點到其余所有節(jié)點的最短路的Dijkstra算法
        public static void Dijkstra
            (
            int startNode,        //IN,需要求到其余所有節(jié)點的最短路的節(jié)點編號
            double[,] weight,     //IN,各節(jié)點之間的路權
            double[] L,           //OUT,startNode節(jié)點到其余所有節(jié)點之間的最短路長
            int[] p               //OUT,startNode節(jié)點到其余所有節(jié)點之間的最短路徑
            )
        {
            int dimensions=weight .GetLength (0);
            List<int> S = new List<int>(dimensions);
            int currentNode;
            S.Add(startNode);
            currentNode = startNode;
            L[startNode] = 0;
            p[startNode] = -1;
            for (int i = 0; i < dimensions; i++)
            {
                if (i != startNode)
                {
                    L[i] = double.MaxValue;
                    p[i] = -1;
                }
            }
            for (int r = 0; r < dimensions; r++)
            {
                for (int j = 0; j < dimensions; j++)
                {
                    if (!S.Contains(j)&&weight [currentNode ,j]<double.MaxValue )
                    {
                        if (L[j] > L[currentNode] + weight[currentNode, j])
                        {
                            L[j] = L[currentNode] + weight[currentNode, j];
                            p[j] = currentNode;
                        }
                    }
                }
                double min = 0;
                for (int i = 0; i < dimensions; i++)
                {
                    if (!S.Contains(i))
                    {
                        min = L[i];
                        break;
                    }
                }
                for (int i = 0; i < dimensions; i++)
                {
                    if (!S.Contains(i))
                    {
                        if (L[i] <= min)
                        {
                            currentNode = i;
                        }
                    }
                }
                S.Add(currentNode);
            }
        }
        //****************************************************************************************************
        
        //*********************************************************************************************************
        //求最短路的Floyd算法
        public static void Floyd
            (
            double[,] weight, //IN,各節(jié)點之間的路權
            double[,] d,      //OUT,各節(jié)點之間的最短路長
            int[,] p          //OUT,各節(jié)點之間的最短路徑
            )
        {
            int rows = weight.GetLength(0);
            int columns = weight.GetLength(1);
            if (rows != columns)
            {
                throw new Exception("維數(shù)錯誤，必須為n階方陣！");
            }
            else
            {
                int dimensions = rows;
                double[,] tempD = new double[dimensions, dimensions];
                int[,] tempP = new int[dimensions, dimensions];
                //step0
                int k = 0;
                for (int i = 0; i < dimensions; i++)
                {
                    for (int j = 0; j < dimensions; j++)
                    {
                        p[i, j] = i;
                        d[i, j] = weight[i, j];
                    }
                }

                //step1
                for (k = 0; k < dimensions; k++)
                {
                    for (int i = 0; i < dimensions; i++)
                    {
                        for (int j = 0; j < dimensions; j++)
                        {
                            tempD[i, j] = d[i, j];
                            tempP[i, j] = p[i, j];
                        }
                    }

                    for (int i = 0; i < dimensions; i++)
                    {
                        for (int j = 0; j < dimensions; j++)
                        {
                            if (tempD[i, j] <= (tempD[i, k] + tempD[k, j]))
                            {
                                d[i, j] = tempD[i, j];
                                p[i, j] = tempP[i, j];
                            }
                            else
                            {
                                d[i, j] = tempD[i, k] + tempD[k, j];
                                p[i, j] = tempP[k, j];
                            }
                        }
                    }
                }
            }

        }
        //***********************************************************************************************

        //**********************************************************************************************
        //最短路徑交通分配
        public static void AllOrNotAssignmentMethod
            (
            double[,] OD,       //IN,需要分配的各節(jié)點之間的OD量
            double[,] weight,   //IN,各節(jié)點之間的路權
            double[,] result    //OUT,各節(jié)點之間流量按最短路徑分配結果
            )
        {
            int dimensions = OD.GetLength(0);
            double[,] tempD = new double[dimensions, dimensions];
            int[,] tempP = new int[dimensions, dimensions];
            Floyd(weight, tempD, tempP);
            for (int i = 0; i < dimensions; i++)
            {
                for (int j = 0; j < dimensions; j++)
                {
                    double ODFlow = OD[i, j];
                    if (ODFlow > 0)
                    {
                        if (tempP[i, j] == i)
                        {
                            result[i, j] += ODFlow;
                        }
                        else
                        {
                            int flag = j;
                            int temp;
                            while (tempP[i, flag] != i)
                            {
                                temp = flag;
                                flag = tempP[i, flag];
                                result[flag, temp] += ODFlow;
                            }
                            result[i, flag] += ODFlow;
                        }