Thread: shortest path problem

ah kk. thank you. god my brain is melting right now. dont know where to start and how to setup all this...

actually i would like to implement it myself. just to practice a little bit.
on paper Dijkstra is so easy but when it comes to an implementation im quite lost.
so maybe lets get more specific. im not that great in abstract thinking

so thats how i would like to do it:

i got a list of structs which contains an ID, a next pointer and a list of structs which contains the edges the current vector has. so it would look something like this

Code:

struct vector
int id
struct vector *next
struct vector edges []

now in my first iteration i check the edges array for the edges.
then i´ll post my result into another list of structs.

Code:

struct result
int fromID
int toID
int jumps (0 at the beginning)
int flag
struct result *next

now i´ll take the first toID out of my result list and search for it in my list of vector structs.
after that i´ll check for the edges again and save/update my result list and set the flag that i visited this vector.

so in pseudocode it may look like this

Code:

method(int start){
int jumps2 = 1;
while( something){


struct vector *ptr = pointer to struct which contains start as id;

k=0;
while(ptr->edges[k] !=NULL){

struct result *ptr2->fromID = ptr->ID;
struct result *ptr2->toID = ptr->edges[k]->ID;
ptr2->jumps = jumps2;
k++;
}
jumps2++;
ptr = the struct which contains the id of the next struct in ptr2;
ptr2=ptr2->next;
}
}

hope you get the idea how i mean to implement this.
would this work?

sorry for some stupid syntax misstakes.

thanks and cya!

Don't know why you have a *next element in your graph, unless this graph is also a list.

I also am not sure what labeling you're doing. In your labeling, you need to label each struct with a number (representing the # of hops) and a node (representing where you came from). There's no next (except maybe in the context of "these labeled but unflagged nodes need to go into a queue"), and there's no toID.

could you perhaps post some code to make it a bit more clear?

im just a bit lost on how to access these structs after i created them without having any of these nextpointers. i have to save them somewhere...
just some code would definetly help me to understand this.

thanks

I'm assuming it's a connected graph. You will need a "start" node, but from there you should be able to get to anywhere else just by following the edges. (If you wanted an adjacency matrix, then you would need to put an ordering on your nodes, but otherwise not really.)