Could anyone explain a few things to me about Dijkstra's algorithm?
I need to calculate the shortest path to a destination in a 2D int array I have. I've tried implementing this into my own code but without understanding of certain things I'm unable to do so. I've looking around and found Dijkstra's algorithm which seems to be what I'm after.
This (gif) image on the wiki link above is what I'm trying to achieve:
http://upload.wikimedia.org/wikipedi..._animation.gif
Code:
1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity ; // Unknown distance function from source to v
4 previous[v] := undefined ; // Previous node in optimal path from source
5 end for ;
6 dist[source] := 0 ; // Distance from source to source
7 Q := the set of all nodes in Graph ;
// All nodes in the graph are unoptimized - thus are in Q
8 while Q is not empty: // The main loop
9 u := vertex in Q with smallest distance in dist[] ;
10 if dist[u] = infinity:
11 break ; // all remaining vertices are inaccessible from source
12 end if ;
13 remove u from Q ;
14 for each neighbor v of u: // where v has not yet been removed from Q.
15 alt := dist[u] + dist_between(u, v) ;
16 if alt < dist[v]: // Relax (u,v,a)
17 dist[v] := alt ;
18 previous[v] := u ;
19 decrease-key v in Q; // Reorder v in the Queue
20 end if ;
21 end for ;
22 end while ;
23 return dist[] ;
24 end Dijkstra.
I'm unclear on most of this and have consequently guessed. I've got a 2D int array with 0's denoting a walkable path and e.g 1's denoting a non-walkable path, and I want to calculate the fastest route to a specific coordinate (let's say 0,0) starting from (8, 14) just like the example (gif) image in the link above.
So, here's a few things I need clearing up:
- The graph, is it my 2D int array?
- What is a vertex? Is it coordinates like 2,1 and 5,7, etc.
- What are nodes? These are vertices, yes?
- When it says q should be the set of all nodes in graph, does that mean I add all the possibly vertices in my graph to q which is a one dimensional array?
- How is it calculating the distance between u and v if it's a vertice
- Is this written for a 1D graph? Is that why it only has one dimension, or is it a placeholder?
- Assuming a vertex is a coordinate (which is what I think it is), I'm unsure how to use it in an array like dist[v]. My first thought is dist[x][y] but I tried that and decided to give up and try another possible solution. (The above question may answer this somewhat.)
Would appreciate any help here! I've not really dealt with algorithms and I need to know this information is accurate or not so much. Cheers!
Re: Could anyone explain a few things to me about Dijkstra's algorithm?
Quote:
Originally Posted by
Icyculyr
- The graph, is it my 2D int array?
- What is a vertex? Is it coordinates like 2,1 and 5,7, etc.
- What are nodes? These are vertices, yes?
- When it says q should be the set of all nodes in graph, does that mean I add all the possibly vertices in my graph to q which is a one dimensional array?
- How is it calculating the distance between u and v if it's a vertice
- Is this written for a 1D graph? Is that why it only has one dimension, or is it a placeholder?
- Assuming a vertex is a coordinate (which is what I think it is), I'm unsure how to use it in an array like dist[v]. My first thought is dist[x][y] but I tried that and decided to give up and try another possible solution. (The above question may answer this somewhat.)
- Yes.
- A vertex is a spot in your 2D array. It can be indicated by a pair of coordinates.
- Yes.
- Basically yes. Using a different data type than a 1D array is best, since arrays aren't typically resized, and you'll be removing members from q. In .NET I would probably start with a Queue. The Queue needs to contain enough information to uniquely identify a vertex in your graph, so here it should contain two coordinates. You can fiddle with arrays to get them to do the job, but it's inefficient and tedious.
- In your case, the distance between neighbors u and v will always be 1. Dijkstra's algorithm is more general than you need, and allows paths of some specified length rather than all equal length paths.
- You seem a bit confused, which is very understandable if arrays are all you've seen as far as dynamically sized data structures go. The notation used in that pseudocode is slightly abstract. For instance, dist[u] does not mean that dist is a one-dimensional array. If in your application you were processing node u = (1, 2), then dist[u] is the (current) distance from the initial node to node (1, 2). You would probably make dist and previous 2D arrays of the same size as your original 2D array.
- See above.
If you haven't worked with complex data types before, you might need to fiddle with them for a while before implementing this algorithm.
Re: Could anyone explain a few things to me about Dijkstra's algorithm?
Quote:
Originally Posted by
jemidiah
- Yes.
- A vertex is a spot in your 2D array. It can be indicated by a pair of coordinates.
- Yes.
- Basically yes. Using a different data type than a 1D array is best, since arrays aren't typically resized, and you'll be removing members from q. In .NET I would probably start with a Queue. The Queue needs to contain enough information to uniquely identify a vertex in your graph, so here it should contain two coordinates. You can fiddle with arrays to get them to do the job, but it's inefficient and tedious.
- In your case, the distance between neighbors u and v will always be 1. Dijkstra's algorithm is more general than you need, and allows paths of some specified length rather than all equal length paths.
- You seem a bit confused, which is very understandable if arrays are all you've seen as far as dynamically sized data structures go. The notation used in that pseudocode is slightly abstract. For instance, dist[u] does not mean that dist is a one-dimensional array. If in your application you were processing node u = (1, 2), then dist[u] is the (current) distance from the initial node to node (1, 2). You would probably make dist and previous 2D arrays of the same size as your original 2D array.
- See above.
If you haven't worked with complex data types before, you might need to fiddle with them for a while before implementing this algorithm.
4) I see. I think an NSMutableArray in Objective C will work well, it's what I've been using and haven't noticed any problems with using it so far. (It's quite flexible.)
5) Ah, right. I see.
6) I'm familiar with dynamically sized data structures (I think) but I think it's mostly to do with the language used in the pseudocode which I'm not very familiar with and also I'm in new territory here. I've never really done anything like this before. Thanks for the help, I suspected that but I wasn't sure or not so I tried both but ending up giving up with the dist[x][y] due to confusion about q and whether or not it should be an array (amongst other things), which I know not to be the case now.
I've two more questions if you don't mind:
- How exactly does Q know which is a valid path and an invalid path? Where does it check if there's a wall or not like it does in the .gif.
- You mentioned Dijkstra's algorithm is more general than I need, do you have any idea of what might be better suited for finest the shortest path in a 2D int array? I've previous tried someone's version of a breadth-first search which worked well but didn't produce the desired result. (It included unnecessary movements.) I've had the Euclidian shortest path theory suggested to me. I'll post what the 2D grid looks like:
Code:
int graph[10][15] = {
{5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5},
{0, 0, 5, 0, 0, 0, 0, 5, 0, 0, 0, 5, 0, 5, 0},
{0, 0, 5, 0, 0, 0, 5, 0, 0, 0, 0, 5, 0, 0, 0},
{0, 0, 5, 5, 5, 0, 5, 0, 5, 0, 5, 0, 0, 5, 0},
{0, 5, 0, 0, 0, 5, 5, 0, 5, 0, 5, 0, 5, 0, 0},
{0, 0, 0, 5, 0, 0, 0, 0, 5, 0, 5, 0, 0, 5, 0},
{0, 5, 0, 0, 5, 0, 5, 0, 5, 0, 5, 0, 5, 0, 0},
{0, 0, 0, 0, 5, 0, 5, 0, 5, 0, 0, 0, 5, 0, 0},
{0, 5, 0, 0, 5, 0, 0, 0, 5, 0, 0, 0, 5, 0, 0},
{5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5},
};
I basically need to calculate from column x row y the fastest path to column 0 row 1. The 5's represent an invalid path and the 0's valid path, although initially it'll almost all be 0's and the user will place the structure's (5's).
Thanks again for all the help, I really appreciate it. It's good knowing this stuff, I think I might be able to figure it out eventually.
EDIT: I think I figured out the answer to #1... when I'm picking the neighbours of U, I need to filter the ones out that I don't want. (By checking my the data in my graph, for example.)
Re: Could anyone explain a few things to me about Dijkstra's algorithm?
Filtering neighbors is fine for (1). As for (2), even with the slightly unnecessary generality, Dijkstra's is probably the best algorithm for your purpose. It's basically a "smart" breadth-first search.
Re: Could anyone explain a few things to me about Dijkstra's algorithm?
Quote:
Originally Posted by
jemidiah
Filtering neighbors is fine for (1). As for (2), even with the slightly unnecessary generality, Dijkstra's is probably the best algorithm for your purpose. It's basically a "smart" breadth-first search.
I see. Thanks.
I've got the code written out. I'll probably have to go to an Objective C forum for help because for some reason when I find the target I was looking for which is 1,0 in this case, previous[u] is empty. (See below)
In the article it said:
Quote:
If we are only interested in a shortest path between vertices source and target, we can terminate the search at line 13 if u = target. Now we can read the shortest path from source to target by iteration:
So, I added this code at line 13 so it'll break after the while loop once it's added the sequence to S.
Code:
1 S := empty sequence
2 u := target
3 while previous[u] is defined:
4 insert u at the beginning of S
5 u := previous[u]
6 end while ;
Each time previous[u] a.k.a previous[1][0] is empty. I've output the previous array to log and it shows vertices (e.g, 2,1) logged but there's nothing in previous[1] at all. It's entirely empty.
Cheers for the help, I've actually got the code compiling and at least looking like it's making sense.
