6
\$\begingroup\$

So, here is the code:

#pragma once
#include <vector>
#include <iostream>
#include <queue>
#include <functional> 

using node = int;
using cost = int;
using arc = std::pair<node, cost>;

using AdjList = std::vector<std::vector<arc>>; // first is node, second is cost


class Graph {
private:
    AdjList adjList;
    std::vector<node> nodes;

public:
    Graph(int n) : nodes{ n },  adjList{ n } {}
    void addEdge(const node v, const node u, const cost c) {
        adjList[v].push_back({ u, c });
        adjList[u].push_back({ v, c });
    }

    std::vector<int> dijkstra(const node n) const {
        std::vector<cost> dist(adjList.size(), INT_MAX);
        std::vector<bool> visited(adjList.size(), false);
        dist[n] = 0;
        std::priority_queue<node, std::vector<node>, std::greater<int>> to_visit;
        to_visit.push(n);
        while (!to_visit.empty()) {
            node v = to_visit.top();
            to_visit.pop();
            visited[v] = true;
            for (const arc& a : adjList[v]) {
                node u = a.first;
                cost c = a.second;
                if (!visited[u] and (dist[u] == INT_MAX or dist[u] > dist[v] + c)) {
                    dist[u] = dist[v] + c;
                    to_visit.push(v);
                }
            }
        }
        return dist;
    }


    friend std::ostream& operator<<(std::ostream& stream, const Graph& g) {
        for (size_t i = 0; i < g.adjList.size(); i++) {
            stream << "node " << i << "\n";
            for (const arc& p : g.adjList[i]) {
                stream << "connected with " << p.first << " cost: " << p.second << " ";
            }
            stream << "\n";
        }
        return stream;
    }


};

I think I did a decent job, but I want to make sure I'm not missing anything. I'm using just a adjacent list for storing the arcs. I was unsure if I should reserve some memory for the vectors there, because maybe it's going to get a little bit slow with the push_back operation, but I also wanted to be able to get rid of the O(n^2) for storing.

\$\endgroup\$
3
  • \$\begingroup\$ That is not Dijkstra algorithm you implemented. \$\endgroup\$ Nov 14, 2020 at 3:45
  • \$\begingroup\$ @MartinYork is it because op's implementation actually works on weighted edges also? Also I think in op's code, same node can be re-inserted into priority queue. correct me if I am wrong. \$\endgroup\$ Jan 1 at 23:30
  • \$\begingroup\$ @theprogrammer No. It is just not Dijkstra. Dijkstra has a distinguishing features that this algorithm does not use. An ordered frontier list of nodes (ordered by shortest distance from start). This does not exist here. It is this frontier list that makes Dijkstra efficient. \$\endgroup\$ Jan 2 at 9:16

1 Answer 1

8
\$\begingroup\$

Graph seems quite reasonable:
But your distance implementation is not an implementation of Dijkstra.

Dijkstra finds only the cheapest path between two nodes (technically).
But I suppose you can use the technique to find the distance from a node to all others nodes. Dijkstra works by finding the cheapest distance to a node then expanding from there (it never re-expands a node, because it does not need to). To do this you need a sorted frontier list so you always expand from the node with the lowest cost to get there and keep track of nodes that were visited.


Some notes:

// Node Id can only by positive.
using node = int;

// Dijkstra assumes all costs are positive.
using cost = int;

Lets have a look at your search:

    // Returning the min distances to all nodes.
    // Sure: but you can not tell what the route to get there is
    //       so this does not help you traverse the graph it only
    //       tells you the shortest distances.
    //       Also how do you tell the difference between a
    //       a distsance of INT_MAX and a node that was never reached.
    std::vector<int> dijkstra(const node n) const {

        // I think this is what is causing you to go wrong.
        // The distance is usually part of the to_visit.
        // You sort the list by the distance.
        std::vector<cost> dist(adjList.size(), INT_MAX);

        // Sure. You need this for dijkstra
        //       In a classic implementation I would have used
        //       std::set<Node> as we don't need (in general) to traverse
        //       the whole graph to find a route from A to B.
        //       Since you are finding the distance to all nodes. This seems
        //       like a better choice.
        std::vector<bool> visited(adjList.size(), false);

        dist[n] = 0;

        // This is a mistake.
        // The order here based on the node-id.
        // It should be based on the cost to get to a node.
        // You always keep it sorted by the cost to get to the node
        // But you may have multiple routes to a node in the list with
        // different costs so after extraction from the list you check
        // if already visited (because if it is already visited then
        // this is not the shortest route).
        //
        // I am sure I could construct a graph that would break this.
        std::priority_queue<node, std::vector<node>, std::greater<int>> to_visit;
        to_visit.push(n);
        while (!to_visit.empty()) {
            node v = to_visit.top();
            to_visit.pop();
            visited[v] = true;
            for (const arc& a : adjList[v]) {
                node u = a.first;
                cost c = a.second;

                // In dijkstra the cost to a node is not known until
                // you actually visit it for the first time (as you may
                // see a node from many other nodes.
                if (!visited[u] and (dist[u] == INT_MAX or dist[u] > dist[v] + c)) {
                    dist[u] = dist[v] + c;
                    to_visit.push(v);
                }
            }
        }
        return dist;
    }

This is what it normally looks like:

    struct DN {
        node  src;
        node  dst;
        cost  c;

        friend bool operator<(DN const& lhs, DN const& rhs) {return lhs.c < rhs.c;}
    };

    std::vector<node> dijkstra(node begin, node end) const
    {
        std::vector<node>       route(adjList.size(), INT_MAX)
        std::set<node>          visited;
        std::priority_queue<DN> frontier;

        frontier.push({INT_MAX, begin, 0});

        while (!frontier.empty()) {
            node v = frontier.top();
            frontier.pop();

            // If we have already been here go to next value.
            if (visited.find(v.dst) != visited.end()]) {
                continue;
            }

            // OK. Found it and save the cost.
            visited.insert(v.dst);
            route[v.dst] = v.src;

            // If we reached the end exit.
            if (v.dst == end) {
                break;
            }

            for (const arc& a : adjList[v.dst]) {
                // Add nodes to frontier list.
                // That is sorted by the cost to the node.
                frontier.push({n, std::get<0>(a), v.c + std::get<1>(a));
            }
        }
        // You can start from the end node
        // and retrace the path the beginning node.
        return route;
    }
\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the feedback. I should have mentioned that I was using dijkstra here to find the cheapest path between u to all of the other nodes. You also pointed out the problem with the implementation: sorting them by id is going to give me wrong results because the invariant of the algorithm is not followed. \$\endgroup\$
    – Norhther
    Nov 14, 2020 at 13:54
  • \$\begingroup\$ You know set::insert() returns both an iterator to the relevant node, and an indicator whether it inserted? find+insert is thus doubled work for no gain. \$\endgroup\$ Nov 15, 2020 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.