// dijkstra.cpp        CMSC 109 Spring 1999 project definition
//
// Given a connected directed graph as input (a set of weighted edges)
// Read in the graph and compute the shortest weighted distance
// from the source (first vertex in the input data) to every other vertex.
// Print the list of vertices in the order read, one per line,
// followed by one space and the distance from the source.
//
// Constraints:
//   Use good Standard C++ style
//   Use C++ STL as much as possible.
//   Do use any library header files of the form <*.h>
//   You may define your own header files and include them "*.h"
//   Justify, by writing a paragraph, if you use any include files
//            <c*> that are C library header files for Standard C++
//
// Hints:   Suggested but not required. You can do it your way.
//          You may use graph_read.cpp and edit it to suit your needs.
//          You may want to put your data structure definitions in
//          a header file, "graph.h" included below, would be such a file.
//

#include <iostream>
using namespace std;

#include "graph.h"

int main(int argc, char *argv[])       // standard main program definition
{

  graph_type G;              // The graph is stored in the object G
  graph_type::iterator vert; // need an iterator through G
  Adj temp;                  // need a temporary Adj list
  Adj::iterator p;           // need a temporary iterator through temp
  
  cout << "dijkstra running" << endl; // trace execution 
  
  if(argc<2) // be sure user supplied a file name
  {
    cout << "no file on command line. Exiting." << endl;
	return 0;
  }

  graph_input(argv[1], G); // input the graph data from file
                           // make a function or use graph_read.cpp

  // initialize each vertex to not done
  for(vert=G.begin(); vert!=G.end(); vert++) vert->set_done(false);
	  
  // pseudo code for Dijkstra's shortest path algorithm (must make this C++)
  
  // while some vertex not done
  //   do u <- vertex with smallest distance that is not done
  //     for each edge v in u's adjacency list
  //       do  if  v's distance is greater than u's distance + v's weight
  //              then v's distance becomes u's distance + v's weight
  //   mark u done

  // print shortest path result
  
  for(vert=G.begin(); vert!=G.end(); vert++)
      cout << vert->get_vertex() << " " << vert->get_distance() << endl;
  cout << endl;  
  
  cout << "dijkstra finished" << endl;
  return 0;
}