Форум программистов
 
О проблемах, например, с регистрацией пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail, а тут можно восстановить пароль.

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Ответ
 
Опции темы
Старый 11.05.2015, 23:11   #1
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию Оптимизация поиска пути между двумя вершинами взвешенного ориентированного графа с помощью bfs

День добрый

Давно я начала над этим думать. Сейчас решил поделиться мыслями..
Начну издалека :
Самый красивый поиск пути на невзвешенном графе - bfs.
Сложность его примерно V*V (или Е, если задаем списком)

Основный принцип, заложенный в bfs - первый путь всегда оптимальный.

Давайте теперь попробуем применить его на взвешенном графе (для начала возьмем неотрицательные ребра).
Для этого нам нужна некая структура, которая позволит за O(logN) (как максимум) вставлять, удалять элемент в упорядоченный ряд. Для этого возьмем кучу (aka очередь с приоритетом). Будешь сортировать по убыванию текущего веса.

Алгоритм получается примерно такой :

Код:
Добавляем в очередь стартовую клетку. 
Пока очередь не пуста
     извлекаем из очереди элемент
     проверяем его соседей, если находим такого, что уже известный путь до этого соседа больше чем, путь до элемента, извлеченного из очереди, + вес ребра (извлеченный элемент, сосед), то запоминаем это как новый путь и помещаем соседа в очередь
Вот и всё!
Код:
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
 
using namespace std;
 
#define INF 1000000
 
ifstream cin("input.txt");
ofstream cout("output.txt");
 
struct st
{
    int p, w;
    friend bool operator < (const st& a, const st& b);
};
 
bool operator < (const st& a, const st& b)
{
    return a.w > b.w;
}
 
st make(int p, int w)
{
    st t;
    t.p = p; t.w = w;
    return t;
}
 
int main()
{
    int n, s, f;
    cin >> n >> s >> f;
    s--; f--;
    vector<vector<int> > v(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> v[i][j];
 
    priority_queue<st>  q;
    q.push(make(s, 0));
 
    vector<int> p(n, INF);
    p[s] = 0;
    while (!q.empty())
    {
        st t = q.top();
        q.pop();
        if (p[t.p] < t.w) continue;
        for (int i = 0; i < n; i++)
        {
            if (v[t.p][i] == -1) continue;
            if (p[i] > p[t.p] + v[t.p][i])
            {
                p[i] = p[t.p] + v[t.p][i];
                q.push(make(i, p[i]));
            }
        }
    }
 
    if (p[f] == INF)
        cout << -1;
    else
        cout << p[f];
    return 0;
}
Вот такой код решает задачу тыц

Сложность.
Очень просто. (V*V*logV) (или E*logV)

Можно написать Дейкстру. Сложность (V*V)
На логарифм я проигрываю..

А теперь давайте возьмем любые ребра (и скажем, что у нас нет цикла отрицательного веса)

Прекрасно. Теперь запускаем тот же самый алгоритм и любуемся, как сложность с (V*V*logV) увеличивается до (V*V*V*logV) (или V*E*logV)

Задача с любыми ребрами решается Форд-Беллманом. И его сложность (V*V*V) или (V*E).

Я снова проигрываю логарифм..


Теперь ради чем темка создавалась :
Не могли бы Вы подсказать, что я не учел?
Можно у меня есть какой-то косяк, который я в упор не вижу?

И не могли бы Вы подсказать, можно ли как-то улучшить эффективность?

Спасибо! Удачи!
Poma][a вне форума Ответить с цитированием
Ответ

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Опции темы


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
кратчайший путь между двумя заданными вершинами графа mimino46 Общие вопросы C/C++ 0 29.11.2013 22:33
Поиск всех путей между двумя вершинами ориент. графа(Язык С) dasterse Помощь студентам 0 13.05.2012 17:18
длина пути между двумя вершинами в графе rubakKa Общие вопросы C/C++ 5 19.12.2010 18:54


Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru
Пеллетный котёл Emtas
котлы EMTAS