Need help with implementing Dijkstra

[spawn2004]

Hi, I am working on a project and I have to implement a graph and to look for the shortest path. As I read so far the best way is with Dijkstra's algorithm. I am trying to do it but i have some problem. Can you please help me with it.
I am reading data from a file and my datastructure is like that:
The hh is file is like that :

class Datastructure {

public:

  Datastructure();

  ~Datastructure();
  // Adds one attraction with id id and name name to the data
  // structure.
  bool add(unsigned int id, std::string name);

  // Tries to find path between from and to. If path is found prints
  // it and return true.
  bool path(unsigned int from, unsigned int to);
  // Adds route between two nodes with distance distance.
  bool route(unsigned int id1, unsigned int distance, unsigned int id2);
  private:

  enum COLOURS{WHITE,GRAY,BLACK};
  struct Node;

  struct Edge
  {
     // Node* startNode;
      Node* destination_Node;
      unsigned int distance;
      Edge():distance(0){}
      Edge(Node* destination, unsigned int distance_):
      destination_Node(destination),distance(distance_){}
  };

  struct Node
  {
      unsigned int id;
      std::string name;
      unsigned int priority;
      enum COLOURS colour;
      std::vector<Edge> path_list;

      Node(unsigned int id_,std::string name_):id(id_),name(name_),priority(0),colour(WHITE){}
      ~Node()
      {
          path_list.clear();
      }
  };

  std::map<unsigned int,Node*> graph_list; //master container
};

I think in the structure "Node" i need also to have an int variable "cost" that will be 0 by default

Now when I call the function

bool path(unsigned int from, unsigned int to);

It need to return true or false because i have a given main() that i need to follow and also to print the that path.
My idea is to have a function:

bool path(unsigned int from, unsigned int to)
{
    vector<int> path_ids;

    reset();
    if(bool Dijkstra(not sure what i need))
    {
       //print path
       return true;
    }
    return false;
}

Reset() should be a function that reset the graph before every search.Also i think that there might be vector that will be passed by reference and will store the all the ids from the shortest path, so after that it will be easy to print them.

Can you please help me with ideas how to implement that.

Thank you in advance for any suggestions or help .

[mike_2000_17]

The typical way to solve the "reset" and "store path" problem for a shortest-path algorithm on a graph is that you do indeed store a "cost" in each node, but you also store a "predecessor" ID in each node. The "predecessor" acts as a back-tracing record of the optimal path. With the "from" and "to" nodes, once you computed the shortest path, you just start from the "to" node and back-track (from "predecessor" to "predecessor") until you are back at the "from" node, and that is your shortest-path trace. Also, another trick is to solve the problem backwards, from "to" to "from", and then, the back-trace from "from" to "to" is in the correct order already.

As for the "reset" function, it is merely a matter of going through all the nodes and edges and resetting all the algorithm-specific values (priority, colour, cost, and predecessor) to whatever is their default / invalid / blank value. The graph itself must be left untouched, i.e., preserve nodes and edges, and their properties.

Btw, if this is more than a homework, you might consider using an off-the-shelf library, such as the Boost Graph Library (BGL) which has several of these algorithms already implemented. That's what "professionals" use.

[spawn2004]

Thank you a lot for the help :)