why this Dijkstra algorithm not working for this particular input?

Question

I have implemented Dijkstra's algorithm. But it does not work when input is the following:

1
6 7
1 2 5
2 3 2
3 4 3
1 4 9
4 5 2
5 6 3
1 6 2
1

I ran it in debug mode, to understand what was wrong. It appeared that the node 5 was not inserted in cell. I can't find out why.

Here the code:

#include<iostream>
#include<vector>
#include<list>
#include <limits>
#include <algorithm>
#include <queue>
#include <set>
#include <stack>
using namespace std;

struct compare
{
    bool operator()(pair<int, int> a, pair<int, int> b) const
    {
        return a.second < b.second;
    }

};

void printResults(vector<int> vec, int starting)
{
    for (int i = 1; i < vec.size(); i++)
    {
        if (vec[i] == numeric_limits<int>::max() && i != starting)
        {
            cout << -1 << " ";
        }
        else if (i != starting)
        {
            cout << vec[i] << " ";
        }
    }

}
void djkstra(vector<vector<pair<int, int>>>&vec, int starting, int number_of_vertices)
{
    int max = numeric_limits<int>::max();
    set <pair<int, int>,compare> queue;
    vector<bool> visited(number_of_vertices + 1, false);
    vector<int> distances(number_of_vertices + 1, max);
    vector<int> parents(number_of_vertices + 1, -1);
    queue.insert(make_pair(starting, 0));
    distances[starting] = 0;
    for (int i = 0; i<number_of_vertices-1; i++)
    {
        pair<int, int> minElem = *queue.begin(); //take min elem
        queue.erase(minElem);
        vector<pair<int, int>> adjacents = vec[minElem.first];//take neighbours
        for (int j = 0; j<adjacents.size(); j++)
        {
            pair<int, int> node = adjacents[j];
            if (!visited[node.first])
            {
                if (distances[node.first]> distances[minElem.first] + node.second) //if we have found smaller distance
                {

                    if (queue.find(make_pair(node.first, distances[node.first])) != queue.end())
                    {
                        queue.erase(make_pair(node.first, distances[node.first]));
                        queue.insert(make_pair(node.first, distances[minElem.first] + node.second));

                    }
                    else
                    {
                        queue.insert(make_pair(node.first, distances[minElem.first] + node.second));
                        cout<<distances[minElem.first] + node.second<<endl;

                    }

                    distances[node.first] = distances[minElem.first] + node.second;
                }

            }

        }
        visited[minElem.first] = true;

    }
    printResults(distances,starting);

}

int main()
{
    int test;
    cin >> test;
    for (int i = 0; i < test; i++)
    {
        int nodes, edges;
        cin >> nodes >> edges;
        vector<vector<pair<int, int>>> vec(nodes + 1);
        for (int j = 0; j < edges; j++)
        {
            int src, des, weight;
            cin >> src >> des >> weight;
            vec[src].push_back(make_pair(des, weight));
            vec[des].push_back(make_pair(src, weight));

        }

        int starting;
        cin >> starting;
        djkstra(vec, starting, nodes);

    }

    system("pause");

    return 0;
}

Answer 1

So, after trying to make sense of your question code, I arrived upon a clean re-write according to the Wikipedia Pseudo-code

I think (because you still never showed the output you get which is supposedly wrong), your cardinal error is just using 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);
    }
}

Which prints the result as:

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

NOTE You had at least one more bug in djkstra [sic] where you did

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

That -1 seems to be completely wrong (if anything, it "should" have been +1 although it was a ginormous code smell to have +1 strewn about all of the code. See how I solved that in my version.

Explanation

std::set<> models a container with unique elements. In this case the weight is the equivalence property and as such, all elements having identical weight are equivalent. At the very start the queue will contain at most 2 elements: 1 starting vertex (distance 0) and 1 of the other vertices that have all been seeded with the same distance (INFINITY; or max in your version).

This is going to sink your algorithm since many nodes are never visited (the algorithms stops as soon the queue is empty).

The fix is 5 letters: s/set/multiset/:

Fixed Version

Prints:

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

---

Answer 2

So, here's your graph:

The output of your program is Live On Coliru:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>

using Graph = boost::adjacency_list<
        boost::vecS, boost::vecS, boost::directedS,
        boost::no_property,
        boost::property<boost::edge_weight_t, int>
    >;

int main() {
    std::cin.exceptions(std::ios::failbit);
    int test; std::cin >> test;
    for (int i = 0; i < test; i++) try {
        int nodes, edges;
        std::cin >> nodes >> edges;
        std::cout << "Nodes:" << nodes << " Edges:" << edges << "\n";

        Graph g(nodes + 1);

        for (int j = 0; j < edges; j++) {
            int src, des, weight;
            std::cin >> src >> des >> weight;
            std::cout << "src:" << src << " des:" << des << " weight:" << weight << "\n";

            add_edge(src, des, weight, g);
        }

        boost::print_graph(g);

        int starting;
        std::cin >> starting;

        std::vector<int> dist(num_vertices(g));
        auto id = get(boost::vertex_index, g);

        dijkstra_shortest_paths(g, starting, 
                weight_map(get(boost::edge_weight, g))
                .distance_map(make_iterator_property_map(dist.begin(), id))
            );

        std::cout << "Distances:\n";
        for (Graph::vertex_descriptor v = 0; v < num_vertices(g); v++) {
            std::cout << starting << " -> " << v << " = " << dist[v] << "\n";
        }
    } catch(std::exception const& e) {
        std::cout << "Error: " << e.what() << "\n";
    }
}

Prints:

Nodes:6 Edges:7
src:1 des:2 weight:5
src:2 des:3 weight:2
src:3 des:4 weight:3
src:1 des:4 weight:9
src:4 des:5 weight:2
src:5 des:6 weight:3
src:1 des:6 weight:2
0 --> 
1 --> 2 4 6 
2 --> 3 
3 --> 4 
4 --> 5 
5 --> 6 
6 --> 
Distances:
1 -> 0 = 2147483647
1 -> 1 = 0
1 -> 2 = 5
1 -> 3 = 7
1 -> 4 = 9
1 -> 5 = 11
1 -> 6 = 2

It's correct!

Here's the output of the algorithm, animating through all reachable target vertices:

It should be pretty self-evident that the correct distances are in fact:

1: 0  
2: 5  
3: 5+2 = 7  
4: 9 (5+2+3 is larger)  
5: 9+2 = 11  
6: 2 (both 5+2+3+2+3 and 9+2+3 are way larger)

UPDATE UNDIRECTED

Yes, if it's undirected, the outcome is different: