/*
 *  dijkstra.h 
 * 
 *  (c) Daniel Jackson 2004. 
 *  CIS 11 Data Structures & Algorithms 
 * 
 
Header file for the class that implements Dijkstra's algorithm. 
 
Dijkstra(graph<Item>* aGraph, std::size_t startVertex = 0); 
  Precondition: aGraph is a graph, and startVertex is a vertex in that graph. 
  Postcondition: The class is prepared to give you information about shortest path and distance from 
    the startVertex to any vertex in aGraph. 
 
void GetDistances(int* array); 
  Precondition: array is a pointer to an int array that is as large or larger than the size of the graph. 
  Postcondition: The array will have graph.size() entries, each one being the distance that vertex 
    is away from the start vertex. If a vertex is unreachable, the distance == -1. 
 
void GetPaths(std::size_t* array); 
  Precondition: array is large enough to hold graph.size() entries. 
  Postcondition: The array will have graph.size() entries, each one being the predecessor of that vertex 
    along the shortest path to that vertex. If a vertex is unreachable, the predecessor > size(). 
 
int Distance(std::size_t target); 
  Precondition: target is a vertex of the graph. 
  Postcondition: The return value will be the distance between start and target vertices, by the shortest  
    path. If target is unreachable, the distance returned is -1. 
 
std::vector<std::size_t> Path(std::size_t target); 
  Precondition: target is a vertex of the graph. 
  Postcondition: The return value is a vector containing the vertices along the shortest path from  
    start to target, in order. If the target is unreachable, the vector is empty. 
 
void ChangeStart(std::size_t newStart); 
  Precondition: newStart is a vertex of the graph. 
  Postcondition: The class is now prepared to give information about shortest path and distance from 
    the newStart vertex 
 
*/ 
 
#ifndef DIJKSTRA_H
#define DIJKSTRA_H

#include <vector>   //Provides vector
#include "graph.h"  //Provides graph 

template <class Item>
class Dijkstra {
  public:
    Dijkstra(graph<Item>* aGraph, std::size_t startVertex = 0);
    void GetDistances(int* array);
    void GetPaths(std::size_t* array);
    int Distance(std::size_t target);
    std::vector<std::size_t> Path(std::size_t target);
    void ChangeStart(std::size_t newStart);
  private:
    std::size_t start;
    graph<Item>* theGraph;
    int* distances;
    std::size_t* predecessor;
    void calculate();
    bool compare(const int lval, const int rval);
};

#include "Dijkstra.cpp"
#endif