Processing math: 100%

単一始点最短パス(BFS)

全ての辺の重みが1の場合の単一始点最短路(単一始点最短パス)は,BFSでO(|V|)で求められる.

説明

単一始点最短パスをDijkstra法で求めることを考える.Dijkstra法では,始点からの最短路長が小さいノードから順に最短路が求まっていった.全ての辺の重みが1の場合,最短路長が小さい順というのはすなわち,始点からBFSをした時に訪れる順番であるため,単に始点からBFSをすることで単一始点最短パスを求めることができる.BFSで全てのノードを1回ずつ訪れるので,計算量はO(|V|)

コード

vector<int> bfs(int node, int n, vector<vector<int>> &g) { queue<pair<int, int>> q; vector<bool> visited(n, false); vector<int> ret(n, -1); visited[node] = true; q.push({node, 0}); while (q.size()) { pair<int, int> v = q.front(); q.pop(); ret[v.first] = v.second; for (int &e: g[v.first]) { if (visited[e]) continue; visited[e] = true; q.push({e, v.second+1}); } } return move(ret); }