Hi
Im trying to understand dijkstra pathfinding. But i need to use it on a grid which im only used to doing on a star. Most implementations look something like this:
const int inf = 1 << 30;
// given adjacency matrix adj, finds shortest path from A to B
int dijk(int A, int B, vector< vector<int> > adj) {
int n = adj.size();
vector<int> dist(n);
vector<bool> vis(n);
for(int i = 0; i < n; ++i) {
dist[i] = inf;
}
dist[A] = 0;
for(int i = 0; i < n; ++i) {
int cur = -1;
for(int j = 0; j < n; ++j) {
if (vis[j]) continue;
if (cur == -1 || dist[j] < dist[cur]) {
cur = j;
}
}
vis[cur] = true;
for(int j = 0; j < n; ++j) {
int path = dist[cur] + adj[cur][j];
if (path < dist[j]) {
dist[j] = path;
}
}
}
return dist[B];
}
What is A and B? Indexes to the start and goal node? It's a graph and not a grid I assume. Can I build a adjacency matrix from a grid and use the above implementation or would there be a completely different implementation for using dijkstra on a grid?
Lets assume my map looks like:
1 0 1
1 0 1
1 1 1
And "0" means impassable node. And I need to pathfind from topleft to topright. How would I setup "vector<vector<int>> adj" so it described this map? A and B? Or is it a stupid way of doing it? I need a minimal pathfind but they seem to always look like the one above.
Thanks for your input!
E