Skip to content

Instantly share code, notes, and snippets.

@vertexclique

vertexclique/dijkstra.cpp

Created November 11, 2013 09:40
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save vertexclique/7410577 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save vertexclique/7410577 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. vertexclique created this gist Nov 11, 2013.
    129 changes: 129 additions & 0 deletions dijkstra.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,129 @@
    //
    // main.cpp
    // dijkstra
    //
    // Created by Mahmut Bulut on 11/11/13.
    // Copyright (c) 2013 Mahmut Bulut. All rights reserved.
    //

    #include <unordered_map>
    #include <vector>
    #include <limits>
    #include <algorithm>
    #include <iostream>

    using namespace std;

    class Graph
    {
    unordered_map<char, const unordered_map<char, int>> vertices;

    public:
    void add_vertex(char name, const unordered_map<char, int>& edges)
    {
    // Insert the connected nodes in unordered map
    vertices.insert(unordered_map<char, const unordered_map<char, int>>::value_type(name, edges));
    }

    vector<char> shortest_path(char start, char finish)
    {
    // Second arguments -> distances
    // Find the smallest distance in the already in closed list and push it in -> previous
    unordered_map<char, int> distances;
    unordered_map<char, char> previous;
    vector<char> nodes; // Open list
    vector<char> path; // Closed list

    auto comparator = [&] (char left, char right) { return distances[left] > distances[right]; };

    for (auto& vertex : vertices)
    {
    if (vertex.first == start)
    {
    distances[vertex.first] = 0;
    }
    else
    {
    distances[vertex.first] = numeric_limits<int>::max();
    }

    nodes.push_back(vertex.first);
    push_heap(begin(nodes), end(nodes), comparator);
    }

    while (!nodes.empty())
    {
    pop_heap(begin(nodes), end(nodes), comparator);
    char smallest = nodes.back();
    nodes.pop_back();

    std::cout << "Open list: ";
    for( std::vector<char>::const_iterator i = nodes.begin(); i != nodes.end(); ++i)
    std::cout << *i << ' ';
    std::cout << std::endl;

    if (smallest == finish)
    {
    while (previous.find(smallest) != end(previous))
    {
    path.push_back(smallest);
    smallest = previous[smallest];
    std::cout << "Closed list: ";
    for( std::vector<char>::const_iterator i = path.begin(); i != path.end(); ++i)
    std::cout << *i << ' ';
    std::cout << std::endl;
    }

    break;
    }

    if (distances[smallest] == numeric_limits<int>::max())
    {
    break;
    }

    for (auto& neighbor : vertices[smallest])
    {
    int alt = distances[smallest] + neighbor.second;
    if (alt < distances[neighbor.first])
    {
    distances[neighbor.first] = alt;
    previous[neighbor.first] = smallest;
    make_heap(begin(nodes), end(nodes), comparator);
    }
    }
    }

    return path;
    }
    };

    int main()
    {
    cout << "@author: Mahmut Bulut" << endl << endl;
    int seq = 0;
    char init_node = 'A';
    char dest_node = 'G';

    Graph g;
    g.add_vertex('A', {{'B', 1}, {'C', 4}, {'F', 2}});
    g.add_vertex('B', {{'E', 2}});
    g.add_vertex('C', {{'G', 2}, {'D', 4}});
    g.add_vertex('D', {});
    g.add_vertex('E', {{'D', 3}});
    g.add_vertex('F', {{'C', 1}, {'G', 4}});
    g.add_vertex('G', {{'E', 5}});

    cout << "As initial node: " << init_node << endl;
    cout << "As goal node: " << dest_node << endl;

    for (char vertex : g.shortest_path(init_node, dest_node))
    {
    cout << "Solution path from goal sequence : " << seq << " Node : " << vertex << endl;
    seq++;
    }

    cout << "Solution path from goal sequence : " << seq << " Node : " << init_node << endl;

    return 0;
    }