Оптимизация поиска пути между двумя вершинами взвешенного ориентированного графа с помощью bfs

[Poma][a]

День добрый

Давно я начала над этим думать. Сейчас решил поделиться мыслями..
Начну издалека :
Самый красивый поиск пути на невзвешенном графе - 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).

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


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

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

Спасибо! Удачи!