/** * Code to find the shortest path between two points using Dijkstra's algorithm * Created by Gamma001 */ // https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#:~:text=Dijkstra's%20algorithm%20(or%20Dijkstra's%20Shortest,and%20published%20three%20years%20later. #include #include #include #include #include #include typedef unsigned int uint; using namespace std; bool valid(int i, int j) { return (i >= 0 && i < 10 && j >= 0 && j < 10); } vector shortest_path(map > graph, int start, int end) { vector empty = {-1}; if(!valid(start/10, start%10) || !valid(end/10, end%10) || start == end) { return empty; } map visited; int path[100]; for(auto &x: graph) { visited[x.first] = false; } queue q; // all adjacent nodes are equally distant from each other so i won't use a priority queue path[start] = start; q.push(start); while(!q.empty()) { int node = q.front(); q.pop(); visited[node] = true; if(node == end) { vector p; while(path[end] != end) { p.push_back(end); end = path[end]; } p.push_back(start); reverse(p.begin(), p.end()); return p; } for(auto &x: graph[node]) { if(!visited[x]) { q.push(x); path[x] = node; } } } return empty; } int main() { map > graph; // adjacenecy matrix for easy conversion to graph int grid[10][10] = { {0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 1, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, }; // 0: empty cell // 1: obstacle int dirs[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} }; // conversion of adjacency matrix to graph for(uint i = 0;i != 10; i++) { for(uint j = 0;j != 10; j++) { if(grid[i][j] == 0) { for(uint k = 0;k != 4; k++) { int n_i = i+dirs[k][0]; int n_j = j+dirs[k][1]; if(valid(n_i, n_j) && grid[n_i][n_j] == 0) { graph[i*10+j].insert(n_i*10+n_j); graph[n_i*10+n_j].insert(i*10+j); } } } } } vector path = shortest_path(graph, 90, 9); if(path[0] == -1) { cout << "No sulution possible"; return 0; } for(int &x: path) { cout << '(' << x/10 << ", " << x%10 << ") "; } return 0; }