1
\$\begingroup\$

This is my implementation of Dijkstra's algorithm. Could you tell me what am I doing wrong and what should be fixed? I was not sure how to keep track of the shortest outgoing edge from a node and I store -1 if there weren't any edges found yet. I am not sure if it is okay.

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

#define MAX_LENGTH 10000

int dijkstra(vector<vector<int>> graph, int source, int target) {
    size_t number_of_nodes = graph.size();
    vector<int> visited;
    map<int, int> lengths_to_nodes; // keeps pairs of lengths like 0:0, 1:20, 2:40

    //fill with max lengths and set source as 0 eg. 0:0 1:10000, 2:10000...
    for (int i = 0; i < number_of_nodes; ++i) {
        lengths_to_nodes.insert(make_pair(i, MAX_LENGTH));
    }
    lengths_to_nodes[source] = 0;

    //set actual node we look path from
    int actual_node = source;

    while (visited.size() < number_of_nodes) {
        //keep track of the shortest path found from this node because it will be
        //the next one we will looking for path from
        //if there was no paths from this node then go back
        int the_shortest_found_now = -1;    /***  IS IT OKEY?  ***/
        int the_shortest_found_now_length = MAX_LENGTH;

        for (int actual_target = 0; actual_target < number_of_nodes; ++actual_target) {
            if (graph[actual_target][actual_node] > 0) {
                int new_length = graph[actual_target][actual_node] + lengths_to_nodes.find(actual_node)->second;
                if (lengths_to_nodes.find(actual_target)->second > new_length) {
                    lengths_to_nodes.find(actual_target)->second = new_length;
                }
                if (new_length < the_shortest_found_now_length) {
                    the_shortest_found_now_length = new_length;
                    the_shortest_found_now = actual_target;
                }
            }
        }
        if (the_shortest_found_now == -1) {
            //if there was no outgoing edges
            actual_node = *(visited.end() - 1);
            visited.erase(visited.end() - 1, visited.end());
        }
        else {
            actual_node = the_shortest_found_now;
            visited.push_back(the_shortest_found_now);
        }
    }
    return lengths_to_nodes.find(target)->second;
}


int main() {
    vector<vector<int>> graph =
            {{{0, 0, 0, 0, 0, 0, 20, 0,},
                     {20, 0, 0, 0, 50, 50, 0, 0,},
                     {0, 0, 0, 10, 0, 0, 0, 0,},
                     {80, 0, 10, 0, 0, 40, 0, 0,},
                     {0, 0, 0, 0, 0, 0, 0, 0,},
                     {0, 10, 10, 0, 30, 0, 0, 0,},
                     {90, 0, 0, 20, 0, 0, 0, 0,},
                     {0, 0, 20, 0, 0, 0, 0, 0,},
             }};

    cout << dijkstra(graph, 0, 7) << endl;

    return 0;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Is your code currently working as intended? Please clarify, as it is not clear from the way your question is worded... \$\endgroup\$ – Phrancis Apr 25 '16 at 18:13
4
\$\begingroup\$

Design

So not really Dijkstra algorithm.

while (visited.size() < number_of_nodes)

This condition may not be met in all graphs (if there is a subset of nodes not connected to other nodes).

Also Dijkstra uses two lists.

  1. List of nodes that have been visited. (starts empty)
  2. A sorted frontier list.

You have the 1st list but seem to cobbling the second list out of thin air each iteration.

Code Review.

int dijkstra(vector<vector<int>> graph, int source, int target) {

Sure. You are returning the shortest length from source to target. But would it not be more interesting to return the path most of the time.

Also a graph being a vector of vector of int is a bit restrictive. You could have created a concept of a graph. Then templatized the algorithm based on the concept. Then writing a wrapper for vector of vector of int to implement the concept would have been trivial.

// Concept.
Graph
    Node const& getNode(int id) const // returns a reference to a node.

Node
    int edgeCount() const             // returns number of outbound edges
    Edge const& getEdge(int id) const // returns a reference to an edge

Edge
    int getDst() const               // returns the id of the dst vertices.
    int getCost() const              // returns the cost from this node to dst.

Algorith for Dijkstra

template<typename Graph>
vector<int> dijkstra(Graph const& graph, int start, int end)
{
    std::vector<int>                seen;
    std::priority_queue<Frontier>   frontierList;

    frontierList.push({start, 0, {start}});

    while(!frontierList.empty())
    {
        Frontier  head = frontierList.top();
        frontierList.pop();

        if (head.location == end) {
            return head.path.append(end);
        }

        if (std::find(std::begin(seen), std::end(seen), head.location) != std::end(seen)) {
            continue;
        }

        for(int loop=0;loop < graph.getNode(head.location).edgeCount(); ++loop) {
            auto const& edge = graph.getNode(head.location).getEdge(loop);
            frontierList.push({edge.getDst(),
                                 head.cost + edge.getCost(),
                                 head.path.append(head.location)});
        }
    }
    return {}; // empty path as none was found.
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for your code. Could you please detail definition of struct Frontier ? \$\endgroup\$ – shrike May 28 '18 at 12:13

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.