C++

ダイクストラ

// TESTしてない！
vector<int> Dijkstra(int start, int N, unordered_map<int, vector<P>> &edges) {
    vector<int> costs(N, -1);
    costs[start] = 0;
    priority_queue<P, vector<P>, greater<>> pq;
    pq.push(P(0, start));

    while (!pq.empty()) {
        int cost, index;
        tie(cost, index) = pq.top(); pq.pop();
        if (cost > costs[index]) continue;

        REPOBJ(itr, edges[index]) {
            int to = itr->first;
            int edge_cost = itr->second;
            int cost_cand = cost + edge_cost;
            if (costs[to] >= 0 && cost_cand >= costs[to]) continue;
            costs[to] = cost_cand;
            pq.push(P(costs[to], to));
        }
    }

    return costs;
}

BFSを用いた最短経路

幅優先探索。計算量はO(V+E)

C - 幅優先探索

' # ', ' . ' でマップされた2次元グリッドで、左上のマスから右したのマスまでの最短経路を求める問題

const int MAX = 55;
const int dy[4]={0,1,0,-1}, dx[4]={1,0,-1,0}; // 4近傍の移動
int H,W;
int goal_y, goal_x;
bool g[MAX][MAX]; // 通れるマスならtrue
bool visited[MAX][MAX];

int bfs(int start_y, int start_x) {
  queue<tuple<int, int, int>> que;
  tuple<int, int, int> vertex = make_tuple(start_y, start_x, 0); // y, x, distance
  visited[start_y][start_x] = true;
  que.push(vertex);
  while(!que.empty()) {
    vertex = que.front();
    int curr_y = get<0>(vertex);
    int curr_x = get<1>(vertex);
    int curr_d = get<2>(vertex);
    que.pop();
    for(int i = 0; i < 4; ++i) {
      int next_y = curr_y + dy[i];
      int next_x = curr_x + dx[i];
      // 範囲外
      if(next_y < 0 || next_y >= H) continue;
      if(next_x < 0 || next_x >= W) continue;

      if(next_y == goal_y && next_x == goal_x) return curr_d+1; // 目的のマスについた

      // 通れないまたはすでに到達済み
      if(!g[next_y][next_x]) continue;
      if(visited[next_y][next_x]) continue;
      que.push(make_tuple(next_y, next_x, curr_d+1));
      visited[next_y][next_x] = true;
    }
  }
  return -1;
}
/***** MAIN *****/
signed main() {
  cin >> H >> W;
  int start_y, start_x;
  cin >> start_y >> start_x;
  cin >> goal_y >> goal_x;
  --start_y; --start_x; --goal_y; --goal_x;
  REP(h, H) {
    REP(w, W) {
      char c;
      cin >> c;
      g[h][w] = (c == '.');
    }
  }
  cout << bfs(start_y,start_x);
  cout << "\\n";
  return 0;
}
/***** MAIN *****/

（' # ' は通れないマスで、' . ' は通れるマス）

DFS（隣接行列・無向グラフ）

深さ優先探索。計算量はO(V+E)。

const int limit = 50;
// n: 頂点の数
// m: 辺の数
int n, m;

// i番目の辺はa[i]とb[i]の間にある
int a[limit], b[limit];
bool graph[limit][limit];
bool visited[limit];

void dfs(int current) {
  visited[current] = true;
  REP(next,n) {
    if(!graph[current][next]) continue;
    if(visited[next]) continue;
    dfs(next);
  }
}
int main() {
	cin >> n >> m;
  REP(i,m) {
    cin >> a[i] >> b[i];
    --a[i]; --b[i];
		// 無,向グラフなので双方向
    graph[a[i]][b[i]] = true;
		graph[b[i]][a[i]] = true;
  }
	dfs(0);
	return 0;
}

ワーシャルフロイド

重み付きグラフの最短経路を求める計算量はO(|V|**3)

j, kを動かして最短経路を見つけて、j→kの経路と、j→i→kの経路を比べる感じ

// d[i][j]にはi→jの重みを入れておく
// d[i][i] → 0, 不可能な辺はINFで初期化
const int MAX = 10;
int d[MAX][MAX];

void WarshallFloyd() {
  REP(i,MAX) REP(j,MAX) REP(k,MAX) {
    d[j][k] = min(d[j][k], d[j][i]+d[i][k]);
  }
}

参考：