典型タグ

最短路モデル

重み付きグラフの距離を計算し、距離の確定条件や最短路木の枝構造から経路・閉路の最適化を行う。

この典型を扱う単元: 最短路モデル

検索別名: Bellman–Ford法、Dijkstra法、shortest path、最短経路

未知問からこの典型を見つける手掛かり

扱う対象
  • dijkstra
  • distance
  • path
  • コスト
  • 距離
  • 辺
  • 道
  • 重み
使う手掛かり
  • frontier
  • multi.?source
  • threshold
  • 最小コスト
  • 最短
  • 移動
保つ不変量
  • dist
  • priority queue
  • 確定したvertex
  • 緩和
  • 距離確定
求めるもの
  • 最小コスト
  • 最小時間
  • 最短距離
適用しない条件
  • syntax
  • 最短(式|文字列)
  • 構文
分類・前提・学習成果

分類と直接の前提

概念上の親: グラフモデルと構造

関連する典型

学習成果と学習単位

  • 許す中継点集合を状態とするDPからFloyd–Warshallを導き、距離行列の更新順・到達不能・負閉路を扱える。

    最短路モデルで学ぶ
  • 辺数を制限した反復緩和から負閉路・正閉路の検出を導き、始点到達性と終点への影響を区別できる。

    最短路モデルで学ぶ
  • 根からの最短路木で第一枝の異なる頂点を結ぶ辺を列挙し、二本の木上経路と合わせて根を通る最小閉路を求められる。

    最短路モデルで学ぶ
  • 非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。

    最短路モデルで学ぶ
  • DAGや使用可能な辺列の順に緩和し、処理済みprefixが表す経路集合を不変量として説明できる。

    最短路モデルで学ぶ

代表問題

この典型の考え方を具体的な問題で確かめるための入口です。

関連問題

この典型が主タグまたは補助タグとして付いている問題です。