Недавно я с удивлением узнал, что алгоритм, которым я пользовался для нахождения минимального пути в графе от одной вершины до остальных, не совпадает с классической дейстрой описанной на википедии или e-maxx. Теперь напишу, как я ищу минимальный путь.

1. Создаем линейный массив cost в котором будем хранить минимальное расстояние до каждой вершины. Инициализируем его БОЛЬШИМИ значениями, а для стартовой вершины запишем 0.
2. Создаем сет интов s, в него мы будем помещать вершины, которые стоит посетить. Изначально s содержит только стартовую вершину.
3. Пока s не пустой выполняем следующее

• берем вершину с начала s, обозначим ее через u, удаляем из сета;
• проходимся по всем ребрам идущим из u. Пусть текущее ребро соединяет вершину u с вершиной v и имеет вес w. Если cost[u]+w < cost[v] тогда обновляем значение для cost[v]= cost[u]+w и добавляем в s вершину v, так как мы нашли до нее "более короткий" путь.

В массиве cost содержаться минимальные расстояния до каждой вершины.

код:

const int inf= INT_MAX/2;
const int MaxN= 2000;
vector<pii> a[MaxN+5]; // список смежности. 
//a[i][j].vartex – номер вершины смежной с i-ой, 
//a[i][j].weight – вес ребра, соединяющего эти вершины.
int cost[MaxN+5];
...
int u,w;
int from; //номер стартовой вершины. 

// заполняем массив БОЛЬШИМИ значениями
for (int i=0; i<=MaxN; i++)
   cost[i]= inf;

set<int> s;
s.clear();
// кладем в начало сета "стартовую вершину" и ставим расстояние до нее 0
s.insert(from); cost[from]= 0; 
int c;

while (!s.empty()) //пока сет не пустой
{
    u= *s.begin(); c= cost[u];
    s.erase(s.begin());
    for (int i=a[u].size()-1; i>=0; i--)
    {// проходимся по всем вершинам смежным с u
       if (cost[a[u][i].vartex]>c+a[u][i].weight) 
       {// если до текущей вершины путь через u "короче"
           cost[a[u][i].vartex]= c+a[u][i].weight; // обновляем значение в массиве
           s.insert(a[u][i].vartex); // добавляем в сет
       }
    }
}

Я пока что точно не оценил сложность алгоритма, но надеюсь на что-то вроде O(E logV), где V – количество вершин, а E – количество ребер в графе. Из возможных преимуществ данного алгоритма можно считать: чуть более краткий код, корректность работы при отрицательном весе ребер.

И собственно вопрос)) можно ли этот алгоритм считать модификацией Дейкстры или он как-то по-другому называется? Или это вообще не ясно что?))

UPD Как уже написали хорошие люди, этот алгоритм неэффективный. так что лучше им не пользововаться