The graph algorithms from the Data Structures and Algorithms courses become short with the STL.
Shortest path on a grid
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
int main() {
vector<string> grid = {"..#", "..."};
int R = grid.size(), C = grid[0].size();
vector<vector<int>> dist(R, vector<int>(C, -1));
int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
queue<pair<int, int>> q;
q.push({0, 0});
dist[0][0] = 0;
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int r = cur.first + dr[k], c = cur.second + dc[k];
if (r < 0 || c < 0 || r >= R || c >= C) continue;
if (grid[r][c] == '#' || dist[r][c] != -1) continue;
dist[r][c] = dist[cur.first][cur.second] + 1;
q.push({r, c});
}
}
cout << "moves to (1, 2): " << dist[1][2] << "\n";
return 0;
}A grid of free cells (.) and walls (#) is a graph: each cell links to its four neighbours. BFS from the start gives the fewest moves to every cell. queue<pair<int, int>> holds cells as (row, column), and the arrays dr and dc list the four directions, so one loop handles all of them. Watch dist fill outwards, ring by ring.
Dijkstra with a priority queue
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
int n = 4;
vector<vector<pair<int, int>>> adj(n);
adj[0].push_back({1, 4}); // an edge 0 -> 1 with weight 4
adj[0].push_back({2, 1});
adj[2].push_back({1, 2});
adj[1].push_back({3, 1});
adj[2].push_back({3, 5});
vector<long long> dist(n, 1000000000);
priority_queue<pair<long long, int>> pq;
dist[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
long long d = -pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > dist[u]) continue; // out of date
for (auto& edge : adj[u]) {
int v = edge.first, w = edge.second;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({-dist[v], v});
}
}
}
for (int v = 0; v < n; v++) cout << dist[v] << " ";
cout << "\n";
return 0;
}Store the graph as vector<vector<pair<int, int>>>: for each vertex, its (neighbour, weight) pairs. Here the edges go one way, from each vertex to later ones. priority_queue takes the largest item first, so push negated distances to get the smallest first. When an entry comes out that is worse than the best known distance, it is out of date: skip it. This is O((n + m) log n), fast enough for 10⁵ vertices.
Grid checks. Test the bounds before reading grid[r][c]: r < 0 || c < 0 || r >= R || c >= C. Otherwise you read outside the grid (StepVioz stops you; a judge says Runtime Error, or worse, Wrong Answer).
Quick check
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.