VPF::Алгоритм Форда - Форум программистов

ReFLeXive

Дата 7.6.2010, 20:46 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 120
Регистрация: 30.3.2009
Где: г. Уфа

Репутация: нет
Всего: 1

Уже неделю мучаюсь с заданием: нужно найти наибольшую пропускную способность пути между парой вершин.
Пропускной способностью пути называется наименьший вес дуги этого пути.
Вот описание алгоритма: Алгоритм Форда
Вот что я написал:

Код


 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;
        }

Для тестов использую простейший граф как на рисунке во вложении.

Проблема вот в чем. если я ищу пропускную способность из 1 в 4, то получается вот что: есть 2 пути (1,2,4 и 1,3,4 ), их пропускные способности равны 1 и 1 соответственно; итого макс. пропускная способность = 2, все верно!
А вот если искать пропускную способность из 1 в 2, то по моему коду при 1м проходе найдется путь 1,2 с пропускной способностью 1, а при 2м проходе путь 1,3,4,2 не будет найден, потому что в методе haveAnyEdge в цикле счетчику присвоится значение 4 (int i = startEdge + 1). Соответственно, после 4й вершины в вершину 2 мы не попадем....
Подскажите плиз какие нить идеи, как мне переделать, чтобы находились все возможные пути в графе между 2 любыми вершинами?

Присоединённый файл ( Кол-во скачиваний: 10 )

__________.png 6,87 Kb

ReFLeXive

Дата 8.6.2010, 12:36 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 120
Регистрация: 30.3.2009
Где: г. Уфа

Репутация: нет
Всего: 1

По сути, мне нужно получить все возможные пути из начальной вершины в конечную! Думал насчет алгоритма Дейкстры...

esperanto

Дата 8.6.2010, 13:11 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 194
Регистрация: 31.5.2003

Репутация: 2
Всего: 4

Цитата(ReFLeXive @ 8.6.2010, 12:36)

Так как путей экспоненциальное число, подойдет любой экспоненциальный алгоритм.

Перебор например

--------------------

B.Sc ->M.Sc.->Microsoft SDE-> (Ph.D. student + Intel SDE + psyсhology B.A) - > Skype SDET

ReFLeXive

Дата 8.6.2010, 20:45 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 120
Регистрация: 30.3.2009
Где: г. Уфа

Репутация: нет
Всего: 1

Цитата(esperanto @ 8.6.2010, 13:11

)

Перебор например

Перебор я по сути написал, вот только он не совсем корректно работает - не все пути находит, тк. при нахождении каждого пути из графа удаляется ребро наименьшего веса, принадлежащее найденному пути...

MaxPayneC

Дата 10.6.2010, 09:17 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 324
Регистрация: 18.2.2006

Репутация: нет
Всего: 9

ReFLeXive, почитайте статью http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%...%B0%D1%84%D0%B5

esperanto

Дата 10.6.2010, 13:18 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 194
Регистрация: 31.5.2003

Репутация: 2
Всего: 4

Цитата(ReFLeXive @ 8.6.2010, 20:45)

Цитата(esperanto @ 8.6.2010, 13:11

)

Перебор например

Так напишите корректный перебор. Кто вам мешает

--------------------

B.Sc ->M.Sc.->Microsoft SDE-> (Ph.D. student + Intel SDE + psyсhology B.A) - > Skype SDET

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »