Help with impletementing dijkstra's Algorithm

[imhiya]

I have two files; one with places then the distance between them.

Example:
Moffat Carlisle 65
Doncaster Hull 76
Northampton Birmingham 90
Leicester Lincoln 82
Sheffield Birmingham 122


I was wanting to use dijkstra's method, but i seem to have a problem because looking pseudo codes to understand it they all ask for a node, then all the connecting nodes. The problem is that the file is unordered so it will keep changing nodes. I thought i could search if it's already in the array/vector. If not then add it, but the problem with this is i don't know how many connecting nodes there is, so i would have to include a expanding varible.

The second file, contains a source city and dest city, which i have to work out the shortest path.

hope you can help!

[Amleto]

so your first part of the problem is to create the graph / nodes.

Think about the properties of the nodes and how you would represent them in code.

[imhiya]

The problem is though that say, the first line has York and Hull, So the first node would be York, with a edge of Hull, then the next Node would be Leeds with a edge of Manchester. The if York comes up again then it will be a seperate node unless i have a method of adding unlimited number of edges for each node.

[Amleto]

ok, so a node has to be able to contain 'unlimited' edges.

class Node
{
public:
 string name;
  list<string> edges;
};

list<Node> nodes;

if nodes has a Node with name == "whatever"
then just add an edge.
else add a new node.

Of course, if you add a node York with edge Hull, you may want to also add a node Hull with edge York.

[imhiya]

Hello, Thanks for the reply. I've worked out it will probably be best to create a adjacency graph for my problem first then impletement dijkstra's

[imhiya]

Hello, Can you help. I used this class that you gave but i've struggling to add anything.

I tried
nodes.name.push_back(str);

but no use, and also i tried
nodes::name.push_back(str);

i also tried to compare sections by trying
nodes[i].name == temp;

but no use, Please help.

[Amleto]

Hello, Can you help. I used this class that you gave but i've struggling to add anything.

I tried
nodes.name.push_back(str);

but no use, and also i tried
nodes::name.push_back(str);

i also tried to compare sections by trying
nodes[i].name == temp;

but no use, Please help.

How do I know what 'temp' is?


name is a string - it has no push_back member.

string astring = "abc";
Node node;
node.name = astring;

You should also realise that the Node class I gave above is far from complete - it has no edge distances in. You should think about how the distances should be associated with an edge.

[geoyar]

If it is not some learning assignment, use boost::graph library, namely boost::adjacent_list.
Set the number of vertises, set edges with properties (the lib has functions to do it) , and use embedded Dijkstra algorithm function.

[imhiya]

If it is not some learning assignment, use boost::graph library, namely boost::adjacent_list.
Set the number of vertises, set edges with properties (the lib has functions to do it) , and use embedded Dijkstra algorithm function.

haha, Thank you. Atleast i know i have a last resort