# 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/Dijkstra.h"
#include "Cost.h"

#include <iostream>
#include <limits>

SCENARIO( "Finding shortest path with numeric edge values" )
{
GIVEN( "A graph of distances between cities" )
{

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;

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 );
}
}
}
}
```