current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 1 down vote favorite

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;
}
share|improve this question
2  
Is your code currently working as intended? Please clarify, as it is not clear from the way your question is worded... – Phrancis Apr 25 at 18:13
up vote 4 down vote

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.
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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