#include "dijkstra.h"
#include <iostream>
#include <iomanip>

//  Constructor makes a VertexInfo object with an "infinite" 
//  distance estimate, shortest path unknown, and no previous vertex
//  on a shortest path from the start.
VertexInfo::VertexInfo(): distance(INF), known(false), previous(-1) {}


//  Computes the shortest path from the given start vertex
//  to all other vertices in the graph represented by the
//  given adjacency matrix.
VertexList dijkstra(AdjacencyMatrix m, int start)
{
    VertexList V(m.size());

    //  Add your code here

    return V;
}

//  Prints the path to this node from the start.
static void print_path(VertexList V, int pos)
{
    if ( V[pos].previous != -1 )
    {
        print_path(V, V[pos].previous);
        std::cout << " -> " << pos;
    }
}

//  Calls the dikstra function and reports the results.
void shortest_path(AdjacencyMatrix m, int start)
{
    VertexList V = dijkstra(m, start);
    std::cout << "Node | Dist. | Path" << std::endl;
    std::cout << "-----+-------+--------" << std::endl;
    for ( unsigned i = 0; i < V.size(); i++ )
    {
        std::cout << setw(4) << i << " | " << setw(5) << V[i].distance << " | ";
        std::cout << start;
        print_path(V, i);
        std::cout << std::endl;
    }
}