Форум программистов [Powered by Invision Power Board]

Код

 public void Ford()
        {
                int S = Convert.ToInt32( textBoxFrom.Text );
                int T = Convert.ToInt32( textBoxTo.Text );
                copyMatr( weightMatrix, weightMatrixCopy);
                while (getPath(S - 1, T - 1, weightMatrixCopy))
                {
                    // действия с найденным путем
                    // найдем в пути минимальное расстояние
                    Top m = new Top();
                    int i_item = -1; // запоминание вершины, для которой удаляем ребро
                    foreach( int i in v_list )
                    {
                        Top n = (Top)map.Get(i);
                        if (n.getWeight() < min)
                        {
                            min = n.getWeight();
                            m = n;
                            i_item = i;
                        }
                        textBoxNum.Text += Convert.ToString(i + 1) + ",";
                    }
                    // найдя мин. расстояние в пути, нужно этот участок удалить, а 
                    // пропускную способность увеличить на величину min
                    capacity += min;
                    textBoxNum.Text += Convert.ToString(T - 1) + "=" + Convert.ToString(min) + "   ";
                    //убираем ребро из матрицы смежности
                    weightMatrix[i_item, m.getVersh()] = 0;
                    weightMatrix[m.getVersh(), i_item] = 0;
                    //воостанавливаем матрицу, т.к. в методе getPath мы работаем с копией 
                    copyMatr( weightMatrix, weightMatrixCopy);
                    // восстанавливаем значения для дальнейшего поиска
                    min = 32767;
                    v_list.Clear();
                    map.Clear();
                }
                textBoxNum.Text = Convert.ToString(S) + "-" + Convert.ToString(T) + ":" + Convert.ToString(capacity) + "\r\n";
            }

        private bool getPath( int S, int T, int[,] matr)
        {
            while (true)
            {
                for (int i = 0; i < count_top; i++)
                {
                    if ((matr[S, i] > 0) && haveAnyEdge( i,T, weightMatrixCopy) )
                    {
                        if (i == T)
                        {
                            // если i-ая вершина последняя в пути
                            Top n = new Top(i, matr[S, i]);
                            map.Add(S, n);
                            v_list.Add(S);
                            return true;
                        }
                        else
                        {
                            // ребро в промежуточную i-ую вершину 
                            Top t = new Top(i, matr[S, i]);
                            map.Add(S, t);
                            v_list.Add(S);
                            matr[S, i] = 0;
                            matr[i, S] = 0;
                            S = i;
                        }
                    }
                }
                if (matr[S, T] == 0)
                {
                    //если больше некуда пойти из данной вершины, то пути нет
                    return false;
                }
            }
            return false;
        }

        private void copyMatr(int[,] from, int[,] to)
        {
            for (int i = 0; i < 25; i++)
            {
                for (int j = 0; j < 25; j++)
                {
                    to[i, j] = from[i, j];
                }
            }
        }

        private bool haveAnyEdge(int startEdge, int endEdge, int[,] wMatr)
        {
            // выдаeт, есть ли какое нить ребро из startEdge. Если нету, то туда не идем
            // если есть, то спокойно идем. Проверка идет на каждом шаге getPath
            if (startEdge == endEdge)
            {
                // костыль, иначе зацикливается, когда в getPath счетчик принимает значение, равное количеству вершин (count_top)
                return true;
            }
            else
            {
                for (int i = startEdge + 1; i < count_top; i++)
                {
                    if (wMatr[startEdge, i] > 0)
                    {
                        return true;
                    }
                }
            }
            return false;
        }