Help with impletementing dijkstra's Algorithm

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!

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.

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.

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

Code:

---

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

---

Code:

---

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.

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

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.

Quote:

---

Originally Posted by 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.

---

How do I know what 'temp' is?


name is a string - it has no push_back member.

Code:

---

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.

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.

Quote:

---

Originally Posted by 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.

---

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