gistfile1.cpp

#include <map>
#include <set>
#include <cfloat>
#include <vector>
#include <algorithm>

using namespace std;

typedef long poiid_t;

class Distance
{
public:
    poiid_t destination;
    float distance;

    Distance(poiid_t _dest, float _dist):
        destination(_dest),
        distance(_dist)
    {}
};


typedef multimap<poiid_t, Distance>::const_iterator DistanceIt;

class Graph
{

private:
        set<poiid_t> nodes;
        multimap<poiid_t, Distance> distances;

public:


    void addDistance(poiid_t sourceNode, poiid_t destNode, float distance)
    {
        nodes.insert(sourceNode);
        nodes.insert(destNode);
        distances.insert(pair<poiid_t, Distance>(sourceNode, Distance(destNode, distance)));
    }

    set<poiid_t> &getNodes()
    {
        return nodes;
    }

    multimap<poiid_t, Distance> &getDistances()
    {
        return distances;
    }


    float getDistance(poiid_t sourceNode, poiid_t destNode)
    {
        float result = getStrictDirectionDistance(sourceNode, destNode);
        return (result < 0) ? getStrictDirectionDistance(destNode, sourceNode) : result;
    }

    float getStrictDirectionDistance(poiid_t sourceNode, poiid_t destNode)
    {

        pair<DistanceIt, DistanceIt> range = distances.equal_range(sourceNode);

        for (DistanceIt it = range.first; it != range.second; ++it)
        {
            if (it->second.destination == destNode)
                return it->second.distance;
        }
        return -1;
    }

};





class Dijkstra {
public:
        struct Comparator
        {
            bool operator ()(const pair<poiid_t, float> &a, const pair<poiid_t, float> &b)
            {
                return a.second > b.second;
            }
        };


        static vector<poiid_t> findPath(Graph graph, poiid_t sourceNode, poiid_t destNode)
        {
                map<poiid_t, float> settledLabels;
                map<poiid_t, float> unsettledLabels;
                map<poiid_t, poiid_t> predecessors;

                for (set<poiid_t>::iterator it = graph.getNodes().begin(); it != graph.getNodes().end(); ++it)
                {
                    poiid_t node = *it;
                    unsettledLabels.insert(pair<poiid_t, float>(node, FLT_MAX));
                }

                poiid_t currentNode = sourceNode;
                float currentLabel = 0;
                while (true)
                {
                    pair<DistanceIt, DistanceIt> range = graph.getDistances().equal_range(currentNode);
                    for (DistanceIt it = range.first; it != range.second; ++it)
                    {
                        Distance link = it->second;
                        float computedLabel = currentLabel + link.distance;
                        map<poiid_t, float>::iterator neighbourIt = unsettledLabels.find(link.destination);
                        if (neighbourIt != unsettledLabels.end() && neighbourIt->second > computedLabel)
                        {
                            unsettledLabels.insert(pair<poiid_t, float>(link.destination, computedLabel));
                            predecessors.insert(pair<poiid_t, float>(link.destination, currentNode));
                        }
                    }



                    unsettledLabels.erase(currentNode);
                    settledLabels[currentNode] = currentLabel;

                    if (unsettledLabels.size() == 0)
                        break;

                    pair<poiid_t, float> el = *std::min_element(unsettledLabels.begin(), unsettledLabels.end(), Comparator());

                    currentNode = el.first;
                    currentLabel = el.second;
                }

                vector<poiid_t> path;
                poiid_t step = destNode;

                while (true)
                {
                    // push front??
                    path.push_back(step);

                    if (!predecessors.count(step))
                        break;

                    step = predecessors[step];
                }

                return path;
        }

};