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

**Edited by suliman, 20 March 2017 - 01:45 AM.**