shortest path problem

Hi everbody!

so here is the problem i got ;) :

i would like to implement some sort of map as a weighted graph. the weight is always 1. im just interested in the "jumps" from vertex to vertex.
it will be probably an Adjacency list.
but know i would like to search for a specific path between two vertices, and i want to determine wich patch is the shortest.
dijkstra i think is a bit to much because as i said i only got weights of 1.
also i would like to abort searching further if the jumps hit a certain amount.

is there a nice and easy way to do this?

thank you!

You can certainly abort within the Dijkstra algorithm if you just have a total weight boundary in your problem. I would start of with the Dijkstra algorithm implementation and modify it to suit my needs. Then I would run some performance analysis and see how I can speed it up for certain trivial cases.

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

Bananorama,

Do you have a copy of Dijkstra's algorithm? It should lead the implementation rather well. Have you got a list data structure handy for implementing the adjacency lists? Have you considered an adjacency matrix? Initializing your graph is probably the most time consuming activity involved in an implementation. Once you get an implementation working you can optimize for special cases....

Best Regards,

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.)