Как работает алгоритм Дейкстры, если используется очередь с максимальным приоритетом? - PullRequest
Новая
       38

Как работает алгоритм Дейкстры, если используется очередь с максимальным приоритетом?

0 голосов
/ 25 апреля 2020

Я недавно искал код для алгоритма Дейкстры. Целью кода было найти путь минимальной стоимости от вершины 1 до вершины N. Я наткнулся на этот рабочий код, когда смотрел на решение проблемы: 

void dijkstra(int start, int n) {
    for(int i = 0; i<n; i++) {
        dist[i] = INF;
        pred[i] = -1;
    }
    dist[start] = 0;  
    priority_queue<ll> q;
    q.push(0);
    int u = 0;
    while(q.size()) {
        u = q.top();
        q.pop();
        for(int end : adj[u]) {
            ll w = weight.at(mp(u, end));
            if(dist[u] + w < dist[end]) {
                dist[end] = dist[u] + w;
                pred[end] = u;
                q.push(end);
            }
        } 
    }
}

Эта программа использует очередь приоритетов в порядок определения вершин, по которым нужно пройти (начиная с вершины 1). Однако приоритетная очередь, реализованная в этом алгоритме, представляет собой стандартную приоритетную очередь C ++, которая является очередью с максимальным приоритетом. Это означает, что самые большие элементы имеют самый высокий приоритет. Тем не менее, я подумал, что в алгоритме Дейкстры мы хотели бы сначала опросить наименьшие вершины? Я не уверен, как использование очереди с максимальным приоритетом работает для этого алгоритма.

1 Ответ

3 голосов
/ 25 апреля 2020

Все, что вы упомянули, верно. Но будь осторожен! u - индекс соседей в этом алгоритме. И, если соседи с более высоким индексом имеют меньшее расстояние, оно будет работать правильно.

Кроме того, вы должны заметить, что очередь приоритетов может быть реализована таким образом, что верхний элемент будет иметь наименьшее значение, используя std::greater<T>.

...