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

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

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


Донат для форума - использовать для поднятия настроения себе и модераторам

А ещё здесь можно купить рекламу за 25 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru

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

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
кратчайший путь между двумя заданными вершинами графа 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


02:44.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.