Нужна помощь в понимании алгоритма Дейкстры - PullRequest
Новая
       9

Нужна помощь в понимании алгоритма Дейкстры

0 голосов
/ 29 ноября 2018

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

DijkstrasAlgorithm(G, w, s)
    InitalizeSingleSource(G, s)
    S = 0
    Q = G.V
    while Q != 0
        u = ExtractMin(Q)
        S = S∪{u}
        for each vertex v ∈ G.Adj[u]
            Relax(u, v, w)

Это код, с которым я заканчиваю: 

DijkstrasAlgorithm(string w, string s) {
    string u;
    string s;
    InitalizeSingleSource(s);
    for (map<string, Vertex*>::iterator it = vertices.begin(); 
    it!=vertices.end(); ++it) {
        minQ.insert(it->first, it->second->key);
    }
    while (u != "empty") {
        u = minQ.extractMin();
        if (!s.empty()) {
            s.append("->");
        }
        s.append(u);
        vector<Neighbor*>::iterator it = adjList[u].begin();
        while (it != adjList[u].end()) {
            relax(u, w, (*it)->weight);
            it++;
        }
    }
    return s;
}

Проблема в том, что этот код не дает мне кратчайшего пути.И, глядя на псевдокод, я не вижу, как это будет.Если бы у меня было 5 вершин (a, b, c, d и e), скажем, я хотел найти кратчайший путь от a до c, и этот кратчайший путь был a-> b-> c.Все, что мог бы сделать этот код, это дать мне c-> e-> d-> b-> a.

Я просто не понимаю здесь логику.Мы инициализируем все ключевые значения вершин в INT_MAX с InitalizeSingleSource (s), за исключением s, который равен 0. Отсюда мы находим минимальное значение ключевых значений вершины вместо использования adjList.

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

По окончании мы выполняем функцию релакс с помощью GE / G.Adj [u], хотя мы и не использовали ребра в нашем измерении минимального пути.

Существует многоэто не имеет смысла для меня, но я предполагаю, что самая странная часть - это установка Q / minQ на основе вершин (GV) вместо ребер (GE).Как это должно найти минимальный путь?Кто-нибудь может объяснить, какую часть алгоритма псевдокода я не понимаю?Спасибо!

РЕДАКТИРОВАТЬ: Включая функцию "расслабиться" тоже. 

relax(string u, string v, int weight) {
    if (vertices[v]->key > (vertices[u]->key + weight)) { 
        vertices[v]->key = (vertices[u]->key + weight);
        vertices[v]->pi = new std::string(u);
    }
}

1 Ответ

0 голосов
/ 29 ноября 2018

Relax уменьшает значения в minQ.

Первый извлеченный узел является источником, так как 0

Теперь все вершины, смежные с источником, помечены кратчайшим из уже обнаруженных путей для их достижения.

Затем одиниз обработанных вершин будет иметь наименьшее значение minQ, и оно будет извлечено и обработано следующим образом.

Теперь вы сможете увидеть, как этот цикл извлечения-> расслабления приводит к графику, на котором каждый узел помеченминимальные затраты для его достижения.

Если вы обновляете указатель на узел без ответа каждый раз, когда происходит релаксация, вы можете просто вернуться назад от нужного целевого узла, чтобы прочитать кратчайший путь.

...