      1  #include <map>
      2  #include <queue>
      3  #include <iostream>
      4
      5  using namespace std;
      6
      7  /**
      8     A utility class representing distance to a given city.
      9  */
     10  class DistanceToCity
     11  {
     12  public:
     13     DistanceToCity();
     14     DistanceToCity(string n, int d);
     15     bool operator<(const DistanceToCity& right) const;
     16     string get_name() const;
     17     int get_distance() const;
     18  private:
     19     string name;
     20     int distance;
     21  };
     22
     23  DistanceToCity::DistanceToCity()
     24  {
     25     name = "";
     26     distance = 0;
     27  }
     28
     29  DistanceToCity::DistanceToCity(string n, int d)
     30  {
     31     name = n;
     32     distance = d;
     33  }
     34
     35  bool DistanceToCity::operator<(const DistanceToCity& right) const
     36  {
     37     return right.distance < distance;
     38  }
     39
     40  inline string DistanceToCity::get_name() const { return name; }
     41
     42  inline int DistanceToCity::get_distance() const { return distance; }
     43
     44  /**
     45     A framework for finding shortest paths
     46     using Dijkstra's shortest path algorithm.
     47  */
     48  class DistanceFinder
     49  {
     50  public:
     51     /**
     52        Set the distance between two cities.
     53        @param from originating city
     54        @param to destination city
     55        @param distance distance between cities
     56     */
     57     void set_distance(string from, string to, int distance);
     58
     59     /**
     60        Produce map of shortest distances.
     61        @param start originating city
     62        @param shortest map of shortest distances from start
     63     */
     64     void find_distance(string start, map<string, int>& shortest);
     65
     66  private:
     67     typedef multimap<string, DistanceToCity> CityMap;
     68     typedef CityMap::iterator Citr;
     69     CityMap cities;
     70  };
     71
     72  void DistanceFinder::set_distance(string from, string to, int distance)
     73  {
     74     cities.insert(CityMap::value_type(from, DistanceToCity(to,
     75        distance)));
     76  }
     77
     78  void DistanceFinder::find_distance(string start,
     79     map<string, int>& shortest)
     80  {
     81     priority_queue<DistanceToCity> que;
     82     que.push(DistanceToCity(start, 0));
     83
     84     while (!que.empty())
     85     {
     86        DistanceToCity new_city = que.top();
     87        que.pop();
     88        if (shortest.count(new_city.get_name()) == 0)
     89        {
     90           int d = new_city.get_distance();
     91           shortest[new_city.get_name()] = d;
     92           Citr p = cities.lower_bound(new_city.get_name());
     93           Citr stop = cities.upper_bound(new_city.get_name());
     94           while (p != stop)
     95           {
     96              DistanceToCity next_destination = (*p).second;
     97              int total_distance = d + next_destination.get_distance();
     98              que.push(DistanceToCity(next_destination.get_name(),
     99                       total_distance));
    100              ++p;
    101           }
    102        }
    103     }
    104  }
    105
    106  int main()
    107  {
    108     DistanceFinder d;
    109     d.set_distance("Pendleton", "Phoenix", 4);
    110     d.set_distance("Pendleton", "Pueblo", 8);
    111     d.set_distance("Pensacola", "Phoenix", 5);
    112     d.set_distance("Peoria", "Pittsburgh", 5);
    113     d.set_distance("Peoria", "Pueblo", 3);
    114     d.set_distance("Phoenix", "Peoria", 4);
    115     d.set_distance("Phoenix", "Pittsburgh", 10);
    116     d.set_distance("Phoenix", "Pueblo", 3);
    117     d.set_distance("Pierre", "Pendleton", 2);
    118     d.set_distance("Pittsburgh", "Pensacola", 4);
    119     d.set_distance("Princeton", "Pittsburgh", 2);
    120     d.set_distance("Pueblo", "Pierre", 3);
    121
    122     map<string, int> shortest;
    123     d.find_distance("Pierre", shortest);
    124     map<string, int>::iterator current = shortest.begin();
    125     map<string, int>::iterator stop = shortest.end();
    126     while (current != stop)
    127     {
    128        pair<string, int> p = *current;
    129        cout << "distance to " << p.first << " is " << p.second << "\n";
    130        ++current;
    131     }
    132     return 0;
    133  }