алгоритм Дейкстры - на с ++?

Dijkstra’s algorithm

Это алгоритм для нахождения кратчайшего маршрута из точки A в точку B.
В вычислительных терминах мы упрощаем маршрут до графа, состоящего из узлов и дуг. Каждый узел представляет собой промежуточную точку, а каждая дуга соединяет два узла и имеет (не отрицательный) вес, представляющий стоимость пути между двумя узлами.

Для реализации алгоритма нужны два списка:

• finished: Набор (узел,стоимость), в котором вы вычислили минимальную стоимость достижения.
• working: Отсортированный список (узел,стоимость), которые были проверены.

Алгоритм:

working.addNode(Start, 0); // No cost to get to start.

for( (node, cost) = working.popHead(); node != End; (node,cost) = working.popHead())
{
    // If we have already processed this node ignore it.
    if (finished.find(node))
    {    continue;
    }

    // We have just removed a node from working.
    // Because it is the top of the list it is guaranteed to be the shortest route to
    // the node. If there is another route to the node it must go through one of the
    // other nodes in the working list which means the cost to reach it will be higher
    // (because working is sorted). Thus we have found the shortest route to the node.

    // As we have found the shortest route to the node save it in finished.
    finished.addNode(node,cost);

    // For each arc leading from this node we need to find where we can get to.
    foreach(arc in node.arcs())
    {
        dest = arc.dest();
        if (NOT (finished.find(dest)))
        {
            // If the node is already in finished then we don't need to worry about it
            // as that will be the shortest route other wise calculate the cost and add
            // this new node to the working list.
            destCost = arc.cost() + cost;
            working.addNode(dest,destCost); // Note. Working is sorted list
        }
    }
} 

Итак, если вы подумаете об этом алгоритме. Допустим, вы путешествуете из Лондона в Манчестер.

finished = {} // empty.
working  = { (London,0) }

Используя следующую матрицу затрат:

                  L    S    O    B    N    M    W
(L) ondon         -    50   60   100  130  -    -
(S) outhampton    50   -    70   -    -    -    -
(O) xford         60   70   -    50   -    200  -
(B) irmingham     100  -    50   -    -    80   110
(N) orwich        130  -    -    -    -    -    -
(M) anchester     -    -    200  80   -    -    80
Ne(W) castle      -    -    -    110  -    80   -

Теперь вы убираете Лондон из рабочего списка (так как он находится во главе) и помещаете его в готовый список. Затем добавьте в рабочий список все города, непосредственно связанные с Лондоном.

finished = { (London,0) }
working  = { (Southampton, 50), (Oxford, 60), (Birmingham, 100), (Norwich,130) }

Считайте, что города в рабочем списке являются внешним краем пузыря, который расширяется от Лондона. Задача алгоритма Дейкстры - продолжать расширять пузырь, пока мы не достигнем Манчестера (не повторяя уже пройденных шагов). Таким образом, пузырь всегда расширяется наружу, и мы всегда расширяем ту часть пузыря, которая меньше всего.

Поэтому следующий шаг - взять начало списка и повторить. Из Саутгемптона есть только два пункта назначения. Обратно в Лондон (который мы отбрасываем, так как он находится в готовом списке) и в Оксфорд. Стоимость проезда до Оксфорда равна 50 + стоимость проезда от Саутгемптона до Оксфорда (обратите внимание, что он дважды присутствует в рабочем списке, но не волнуйтесь, мы отбросим его позже как неоптимальный маршрут).

finished = { (London,0), (Southampton,50) }
working  = { (Oxford, 60), (Birmingham, 100), (Oxford, 120), (Norwich,130) }

Итак, повторите цикл. Во главе списка находится Оксфорд. Из Оксфорда мы можем поехать в Манчестер(200), Бирмингем(50) или обратно в Лондон(60) или Саутгемптон (помните, что нам нужно добавить стоимость проезда до Оксфорда к каждому из этих расходов выше. Обратите внимание, что из Оксфорда мы могли бы поехать в Саутгемптон, но мы уже нашли кратчайший путь в Саутгемптон, поэтому обработка не требуется) В результате мы получим:

finished = { (London,0), (Southampton,50), (Oxford, 60) }
working  = { (Birmingham, 100), (Birmingham,110), (Oxford, 120), (Norwich,130), (Manchester,200)}

Обратите внимание, что теперь в рабочем списке есть Манчестер (это наш пункт назначения). Но нам нужно продолжать работу, так как мы можем найти более короткий маршрут. Итак, теперь мы расширяемся из Бирмингема. Оттуда мы можем поехать в Оксфорд(50), Манчестер(80), Лондон(100), Ньюкасл(110). Добавив стоимость проезда до Бирмингема, мы получаем:

finished = { (London,0), (Southampton,50), (Oxford, 60), (Birmingham, 100) }
working  = { (Birmingham,110), (Oxford, 120), (Norwich,130), {Manchester, 180), (Manchester,200), (Newcastle, 210)}

Следующие два узла. Оксфорд и Бирмингем уже находятся в готовом списке, поэтому мы можем их проигнорировать. Таким образом, если не существует маршрута из Норвича в Манчестер, который составляет менее 50 миль, мы достигнем Манчестера в следующей итерации.

Реализация на c ++

#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
using namespace std;

#define pb push_back
#define mp make_pair
#define MAXN 50100
#define INF 1000000000

int N, M, d[MAXN]; vector<int> G[MAXN], C[MAXN];
set< pair<int, int> > T;

void solve(void)
{
    int i, j, k, val, x;

    for(i = 2; i <= N; i++) d[i] = INF;
    T.insert( mp(0, 1) );

    while( T.size() > 0 )
    {
        val = (*T.begin()).first, x = (*T.begin()).second;
        T.erase(*T.begin());
        for(i = 0; i < G[x].size(); i++)
         if(d[ G[x][i] ] > val + C[x][i] )
            d[ G[x][i] ] = val + C[x][i], T.insert(mp(d[G[x][i]],G[x][i]));
    }
}

int main(void)
{
    freopen("dijkstra.in", "rt", stdin);
    freopen("dijkstra.out", "wt", stdout);

    int i, a, b, c;

    scanf("%d %d\n", &N, &M);

    for(i = 1; i <= M; i++)
        scanf("%d %d %d\n", &a, &b, &c), G[a].pb(b), C[a].pb(c);

    solve();

    for(i = 2; i <= N; i++)
        printf("%d ", d[i] == INF ? 0 : d[i]);

    return 0;
}