Sans Pareil Technologies, Inc.

Key To Your Business

Lab 9 - Dijkstra's Algorithm


In this lab session we will implement Dijkstra's shortest path algorithm for finding one of the shortest path's between a source and target vertex in a weighted graph. We use the Graph data structure developed in Lab 8 and implement the algorithm using just the iterators and public interface exposed by the graph.
Dijkstra's Algorithm 
#pragma once

#include <set>
#include <stack>
#include <vector>

namespace csc280::shortestPath
{
  using Pair = std::pair<std::size_t, std::size_t>;
  using Pairs = std::vector<Pair>;

  template <template<typename, typename> typename Graph, typename V,
    typename E, typename Less = std::less<E>>
  std::pair<Pairs, E> dijkstra( const Graph<V,E>& graph, const V& source, 
    const V& destination, const E& minValue, const E& maxValue, const Less& less = {} )
  {
    std::vector<E> distances( graph.size(), maxValue );
    Pairs previous;
    previous.reserve( graph.size() );

    using QPair = std::pair<E, std::size_t>;
    using Queue = std::set<QPair>;
    Queue queue;

    const auto siter = graph.find( source );
    const auto sindex = std::distance( graph.cbegin(), siter );
    distances[sindex] = minValue;
    queue.insert( { minValue, sindex } );

    const auto diter = graph.find( destination );
    const auto dindex = std::distance( graph.cbegin(), diter );
    bool found = false;

    while ( !queue.empty() )
    {
      const auto begin = queue.cbegin();
      std::size_t index = begin->second;

      if ( index == dindex )
      {
        found = true;
        break;
      }

      queue.erase( begin );
      const auto& current = graph[index];

      for ( auto iter = graph.cbegin( current ); iter != graph.cend( current ); ++iter )
      {
        const auto distance = distances[index] + *iter;
        if ( less( distance, distances[iter.index()] ) )
        {
          distances[iter.index()] = distance;
          previous.push_back( { index, iter.index() } );
          queue.insert( { distance, iter.index() } );
        }
      }
    }

    if ( !found ) return { Pairs{}, maxValue };

    std::stack<Pair> stack;
    int index = dindex;
    for ( auto riter = previous.crbegin(); riter != previous.crend(); ++riter )
    {
      if ( index == riter->second )
      {
        index = riter->first;
        stack.push( *riter );
      }
    }

    Pairs paths;
    while ( !stack.empty() )
    {
      paths.push_back( stack.top() );
      stack.pop();
    }
    return { std::move( paths ), distances[dindex] };
  }
}
Cost 
A simple data structure that represents a complex cost. We will imagine that the cost of driving from one place to another is a combination of various factors - distance, time to cover that distance (based on speed limits, traffic conditions etc), and the amount in tolls to be paid on a particular route. We will use this structure to ensure that the Dijkstra's algorithm implementation works properly with complex data types and not just with numbers.
// Cost.h
#pragma once

#include <ostream>

namespace csc280::test
{
  struct Cost
  {
    float distance;
    uint64_t duration;
    float tolls;

    float cost() const
    {
      return ( duration * 0.5 ) +
        ( distance * 0.3 ) + ( tolls * 0.2 );
    }

    Cost operator+ ( const Cost& rhs ) const
    {
      return Cost{ distance + rhs.distance, duration + rhs.duration, tolls + rhs.tolls };
    }
  };

  inline bool operator< ( const Cost& lhs, const Cost& rhs )
  {
    return lhs.cost() < rhs.cost();
  }

  inline bool operator== ( const Cost& lhs, const Cost& rhs )
  {
    return lhs.distance == rhs.distance &&
      lhs.duration == rhs.duration &&
      lhs.tolls == rhs.tolls;
  }

  inline bool operator!= ( const Cost& lhs, const Cost& rhs )
  {
    return !( lhs == rhs );
  }

  inline std::ostream& operator<< ( std::ostream& os, const Cost& cost )
  {
    os << "Cost - distance: " << cost.distance <<
      ", duration: " << cost.duration <<
      ", tolls: " << cost.tolls;
    return os;
  }
}
Test 
// Dijkstra.cpp
#include "catch.hpp"
#include "../main/AdjacencyListGraph.h"
#include "../main/Dijkstra.h"
#include "Cost.h"

#include <iostream>
#include <limits>

SCENARIO( "Finding shortest path with numeric edge values" )
{
  GIVEN( "A graph of distances between cities" )
  {
    csc280::AdjacencyListGraph<std::string, std::size_t> graph;

    WHEN( "When shortest path is second of possible paths" )
    {
      graph.emplaceEdge( "Chicago", "Indianapolis", 200 );
      graph.emplaceEdge( "Indianapolis", "Cleveland", 300 );
      graph.emplaceEdge( "Cleveland", "Pittsburg", 300 );
      graph.emplaceEdge( "Pittsburg", "New York", 300 );
      graph.emplaceEdge( "Chicago", "Detroit", 300 );
      graph.emplaceEdge( "Detroit", "Buffalo", 500 );
      graph.emplaceEdge( "Buffalo", "New York", 200 );

      const std::string start = "Chicago";
      const std::string destination = "New York";
      using limit = std::numeric_limits<std::size_t>;
      const auto result = csc280::shortestPath::dijkstra(
        graph, start, destination, limit::min(), limit::max() );
      REQUIRE( 1000 == result.second );

      THEN( "Checking path by indices" )
      {
        std::vector<std::size_t> indices;
        indices.reserve( result.first.size() + 2 );
        indices.push_back( result.first.front().first );
        for ( const auto pair : result.first )
        {
          indices.push_back( pair.second );
        }

        const std::vector<std::size_t> expected{ 0, 5, 6, 4 };
        REQUIRE( expected == indices );
      }

      AND_THEN( "Checking path by city names" )
      {
        std::vector<std::string> cities;
        cities.reserve( result.first.size() + 2 );
        cities.push_back( graph[result.first.front().first] );

        for ( const auto pair : result.first )
        {
          cities.push_back( graph[pair.second] );
        }

        const std::vector<std::string> expected{ "Chicago", "Detroit", "Buffalo", "New York" };
        REQUIRE( expected == cities );
      }
    }

    WHEN( "When shortest path is first of possible paths" )
    {
      graph.emplaceEdge( "Chicago", "Indianapolis", 100 );
      graph.emplaceEdge( "Indianapolis", "Cleveland", 200 );
      graph.emplaceEdge( "Cleveland", "Pittsburg", 300 );
      graph.emplaceEdge( "Pittsburg", "New York", 300 );
      graph.emplaceEdge( "Chicago", "Detroit", 300 );
      graph.emplaceEdge( "Detroit", "Buffalo", 500 );
      graph.emplaceEdge( "Buffalo", "New York", 200 );

      const std::string start = "Chicago";
      const std::string destination = "New York";
      using limit = std::numeric_limits<std::size_t>;
      const auto result = csc280::shortestPath::dijkstra(
        graph, start, destination, limit::min(), limit::max() );
      REQUIRE( 900 == result.second );

      THEN( "Checking path by indices" )
      {
        std::vector<std::size_t> indices;
        indices.reserve( result.first.size() + 2 );
        indices.push_back( result.first.front().first );
        for ( const auto pair : result.first )
        {
          indices.push_back( pair.second );
        }

        const std::vector<std::size_t> expected{ 0, 1, 2, 3, 4 };
        REQUIRE( expected == indices );
      }

      AND_THEN( "Checking path by city names" )
      {
        std::vector<std::string> cities;
        cities.reserve( result.first.size() + 2 );
        cities.push_back( graph[result.first.front().first] );

        for ( const auto pair : result.first )
        {
          cities.push_back( graph[pair.second] );
        }

        const std::vector<std::string> expected{ "Chicago", "Indianapolis", "Cleveland", "Pittsburg", "New York" };
        REQUIRE( expected == cities );
      }
    }
  }
}

SCENARIO( "Finding shortest path with complex edge values" )
{
  GIVEN( "A graph of driving distance/time/cost between cities" )
  {
    using csc280::test::Cost;
    csc280::AdjacencyListGraph<std::string, Cost> graph;

    WHEN( "Adding a route between Chicago and New York" )
    {
      graph.emplaceEdge( "Chicago", "Indianapolis", Cost{ 200.0, 180, 25.0 } );
      graph.emplaceEdge( "Indianapolis", "Cleveland", Cost{ 300.0, 200, 50.0 } );
      graph.emplaceEdge( "Cleveland", "Pittsburg", Cost{ 300.0, 250, 35.0 } );
      graph.emplaceEdge( "Pittsburg", "New York", Cost{ 300.0, 280, 60.0 } );
      graph.emplaceEdge( "Chicago", "Detroit", Cost{ 300.0, 270, 25.0 } );
      graph.emplaceEdge( "Detroit", "Buffalo", Cost{ 500.0, 500, 10.0 } );
      graph.emplaceEdge( "Buffalo", "New York", Cost{ 200.0, 180, 25.0 } );

      const Cost min{ 0.0, 0, 0 };
      const Cost max{ 100000.0, 1000000, 1000000 };
      const std::string start = "Chicago";
      const std::string destination = "New York";
      const auto result = csc280::shortestPath::dijkstra(
        graph, start, destination, min, max );

      std::cout << "Shortest path vertices(1) ";
      for ( const auto& pair : result.first )
      {
        std::cout << pair.first << " -> " << pair.second << ", ";
      }
      std::cout << "\n";

      THEN( "Checking path by indices" )
      {
        std::vector<std::size_t> indices;
        indices.reserve( result.first.size() + 2 );
        indices.push_back( result.first.front().first );
        for ( const auto pair : result.first )
        {
          indices.push_back( pair.second );
        }

        const std::vector<std::size_t> expected{ 0, 5, 6, 4 };
        REQUIRE( expected == indices );
      }
    }

    AND_WHEN( "Adding a route between Chicago and New York with time variation" )
    {
      graph.emplaceEdge( "Chicago", "Indianapolis", Cost{ 200.0, 180, 25.0 } );
      graph.emplaceEdge( "Indianapolis", "Cleveland", Cost{ 300.0, 200, 50.0 } );
      graph.emplaceEdge( "Cleveland", "Pittsburg", Cost{ 300.0, 250, 35.0 } );
      graph.emplaceEdge( "Pittsburg", "New York", Cost{ 300.0, 280, 60.0 } );
      graph.emplaceEdge( "Chicago", "Detroit", Cost{ 300.0, 270, 25.0 } );
      graph.emplaceEdge( "Detroit", "Buffalo", Cost{ 500.0, 500, 10.0 } );
      graph.emplaceEdge( "Buffalo", "New York", Cost{ 200.0, 280, 25.0 } );

      const Cost min{ 0.0, 0, 0 };
      const Cost max{ 100000.0, 1000000, 1000000 };
      const std::string start = "Chicago";
      const std::string destination = "New York";
      const auto result = csc280::shortestPath::dijkstra(
        graph, start, destination, min, max );

      std::cout << "Shortest path vertices(2) ";
      for ( const auto& pair : result.first )
      {
        std::cout << pair.first << " -> " << pair.second << ", ";
      }
      std::cout << "\n";

      THEN( "Checking path by indices" )
      {
        std::vector<std::size_t> indices;
        indices.reserve( result.first.size() + 2 );
        indices.push_back( result.first.front().first );
        for ( const auto pair : result.first )
        {
          indices.push_back( pair.second );
        }

        const std::vector<std::size_t> expected{ 0, 1, 2, 3, 4 };
        REQUIRE( expected == indices );
      }
    }
  }
}