为什么此Dijkstra算法不适用于此特定输入？

所以，经过努力，以化妆的感觉你的代码有问题，我根据在到达一个干净重新写维基百科伪代码

我认为（因为您仍然从未显示过您认为错误的输出），您的主要错误只是使用了set<>：

Bugged Version

#include <algorithm>
#include <iostream>
#include <limits>
#include <list>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <cassert>

using Vertex  = unsigned;
using Weight  = double;

struct OutEdge {
    Vertex node;
    Weight weight;
    bool operator<(OutEdge const& o) const { return weight < o.weight; }
};

using OutEdges     = std::vector<OutEdge>;
using AdjList      = std::vector<OutEdges>;
using Distances    = std::vector<Weight>;
using Predecessors = std::vector<Vertex>;

static Weight const INFINITY = std::numeric_limits<Weight>::max();
static Vertex const UNDEFINED {-1u};

using namespace std;

void print_graph(AdjList const& graph) {
    for (Vertex v = 1; v < graph.size(); v++) {
        std::cout << v << " -";
        for (auto& adj : graph[v])
            std::cout << " " << adj.node << "(" << adj.weight << ")";
        std::cout << "\n";
    }
}

void printResults(Distances const& dist, Vertex starting) {
    for (Vertex v = 0; v < dist.size(); v++) {
        std::cout << starting << " -> " << v << ": ";
        if (dist[v] == INFINITY && v != starting) {
            cout << -1 << " ";
        } else { // if (v != starting) {
            cout << dist[v] << " ";
        }
        std::cout << "\n";
    }
}

Distances dijkstra(AdjList const& graph, Vertex source) {
    std::set<OutEdge> Q;

    vector<bool> visited(graph.size(), false);
    Distances    dist(graph.size(), INFINITY);  // Unkown distance from source
    Predecessors prev(graph.size(), UNDEFINED); // Previous node in optimal path from source

    dist[source] = 0; // Distance from source to source

    for (Vertex v = 1; v < graph.size(); v++)
        Q.insert({v, dist[v]});

    while (!Q.empty()) {
        Vertex u = Q.begin()->node;
        visited[u] = true;
        Q.erase(Q.begin());

        for (auto& v : graph[u]) { // for each neighbour
            if (visited[v.node]) // where v is still in Q.
                continue;

            Weight alt = dist[u] + v.weight;

            if (alt < dist[v.node]) // A short path to v has been found
            {
                dist[v.node] = alt;
                prev[v.node] = u;

                // update prio
                auto it = std::find_if(Q.begin(), Q.end(), [&](auto& oe) { return oe.node == v.node; });
                if (it != Q.end()) {
                    Q.erase(it);
                    Q.insert({v.node, alt});
                }
            }
        }
    }

    return dist;
}

int main() {
    size_t test;
    cin >> test;
    for (size_t i = 0; i < test; i++) {
        size_t nodes, edges;
        cin >> nodes >> edges;
        nodes += 1; // hack to avoid converting ids to base-0

        AdjList adj(nodes);
        for (size_t j = 0; j < edges; j++) {
            Vertex src, des;
            Weight weight;

            cin >> src >> des >> weight;
            assert(weight>=0);

            adj[src].push_back({des, weight});
            adj[des].push_back({src, weight});
        }

        print_graph(adj);

        Vertex starting;
        cin >> starting;
        auto d = dijkstra(adj, starting);
        printResults(d, starting);
    }
}

将结果打印为：

1 -> 0: -1 
1 -> 1: 0 
1 -> 2: 5 
1 -> 3: 7 
1 -> 4: 9 
1 -> 5: -1 
1 -> 6: 2 

注意您在djkstra[sic]中至少还有一个错误

for (int i = 0; i<number_of_vertices-1; i++)

这-1似乎是完全错误的（如果有的话，+1尽管+1散布了所有代码，这是一个巨大的代码味道，但“应该”已经存在了。请参阅如何在我的版本中解决该问题。

说明

std::set<>使用唯一元素对容器建模。在这种情况下，重量是等效属性，因此，所有具有相同重量的元素都是等效的。从一开始，队列将最多包含2个元素：1个起始顶点（距离0）和所有其他顶点以相同距离（INFINITY；或max在您的版本中）播种的其他顶点中的1个。

这将沉没您的算法，因为永远不会访问许多节点（一旦队列为空，算法就会停止）。

解决方法是5个字母s/set/multiset/：：

Fixed Version

印刷品：

1 -> 0: -1 
1 -> 1: 0 
1 -> 2: 5 
1 -> 3: 7 
1 -> 4: 7 
1 -> 5: 5 
1 -> 6: 2