最短路さいたんろの基本きほん

date2026-07-14document_iddoc_cfb7aa8638aa4a6bd358edf029cbe4c6description最短路問題の定義を厳密に整理し、BFS、ダイクストラ法、負辺を扱う方法の適用条件を説明する。prerequisitesグラフの基本 / DFSとBFSの基本 / 計算量の基本type講義statusactive

algorithmgraphundergraduatelecture

1導入どうにゅう

この講義こうぎでは、辺数へんすうまたは辺重へんおもみの総和そうわを最小化さいしょうかする最短路問題さいたんろもんだいを定式化ていしきかし、BFS、ダイクストラ法ほう、負辺ふへんを扱あつかえる方法ほうほうの適用条件てきようじょうけんを説明せつめいする。

グラフの頂点ちょうてん・辺へん・歩道ほどう・道みちと、BFSの層構造そうこうぞうを前提ぜんていとする。

data/lecture/information/graph/graph-basics.lecture.n.md data/lecture/information/algorithm/search/dfs-and-bfs-basics.lecture.n.md

2グラフと経路けいろの定義ていぎ

有限ゆうげんグラフ $G = (V, E)$ を考かんがえる。無向むこうグラフでは辺へん ${u, v}$ に向むきがなく、有向ゆうこうグラフでは有向辺ゆうこうへん $(u, v)$ は $u$ から $v$ への移動いどうだけを許ゆるす。

$s$ から $t$ への歩道ほどうwalkとは、 $v_{0} = s, v_{1}, \dots, v_{k} = t$ という頂点列ちょうてんれつであり、連続れんぞくする二頂点にちょうてんを結むすぶ辺へんが $E$ に属ぞくするものをいう。有向ゆうこうグラフでは辺へんの向むきも一致いっちしなければならない。頂点ちょうてんを反復はんぷくしない歩道ほどうを道みちpathと呼よぶ。辺数へんすうは $k$ である。

辺重へんおもみ関数かんすうedge-weight functionとは、各辺かくへんに実数じっすうを対応たいおうさせる関数かんすう $w : E \to R$ である。歩道ほどう $P = (v_{0}, \dots, v_{k})$ の費用ひようcostを

c (P) = \sum_{i = 1}^{k} w (v_{i - 1}, v_{i})

と定義ていぎする。無向辺むこうへんでは $w (v_{i - 1}, v_{i})$ を、その二頂点にちょうてんを結むすぶ無向辺むこうへんの重おもみと解釈かいしゃくする。辺数へんすうを最小化さいしょうかする問題もんだいは、すべての辺へんに重おもみ $1$ を与あたえた場合ばあいに一致いっちする。

3距離きょりと到達不能とうたつふのう

$s$ から $t$ への歩道ほどうの費用ひようの下限かげんを

δ (s, t) = \inf {c (P) ∣ P isan s [PARSE ERROR: Undefined("RBrace")] t walk}

と定義ていぎする。 $s$ から $t$ へ到達不能とうたつふのうである場合ばあいは、候補こうほの集合しゅうごうが空くうであるため $δ (s, t) = + \infty$ とする。

閉歩道へいほどうclosed walkとは、始点してんと終点しゅうてんが一致いっちする歩道ほどうである。閉歩道へいほどうのうち、始点してん・終点しゅうてんを除のぞいて頂点ちょうてんを反復はんぷくせず、辺へんも反復はんぷくしないものを閉路へいろcycleと呼よぶ。有向ゆうこうグラフの負ふの閉歩道へいほどうは、その分解ぶんかいに負閉路ふへいろを少すくなくとも一ひとつ含ふくむ。

$s$ から到達可能とうたつかのうで、かつ $t$ へ到達可能とうたつかのうな負ふの閉歩道へいほどうが存在そんざいすると、その閉歩道へいほどうを任意回数にんいかいすうだけ反復はんぷくできる。この場合ばあいは $δ (s, t) = - \infty$ であり、最小費用さいしょうひようを達成たっせいする歩道ほどうは存在そんざいしない。無向むこうグラフでは、負辺ふへんを往復おうふくする閉歩道へいほどうの費用ひようが負ふになるため、その負辺ふへんを $s$ から $t$ への経路けいろに利用りようできるなら距離きょりは $- \infty$ である。

関連かんれんする負閉路ふへいろがなく、 $t$ が到達可能とうたつかのうであるとする。任意にんいの $s$ から $t$ への歩道ほどうが頂点ちょうてんを反復はんぷくするなら、その間あいだの閉歩道へいほどうの費用ひようは非負ひふであり、これを除去じょきょしても費用ひようは増加ぞうかしない。この操作そうさを反復はんぷくすると道みちを得える。有限ゆうげんグラフの $s$ から $t$ への道みちは有限個ゆうげんこなので、その費用ひようの最小値さいしょうちを達成たっせいする道みちが存在そんざいする。この道みちを $s$ から $t$ への最短路さいたんろと呼よぶ。

4重おもみによる方法ほうほうの選択せんたく

4.1等ひとしい辺重へんおもみ

すべての辺重へんおもみが同おなじ正せいの定数ていすう $c > 0$ である場合ばあい、費用ひようは辺数へんすうの $c$ 倍ばいなので、費用ひようの最小化さいしょうかは辺数へんすうの最小化さいしょうかに一致いっちする。BFSは始点してんからの辺数へんすうが非減少ひげんしょうとなる順序じゅんじょで頂点ちょうてんを処理しょりするため、各到達可能頂点かくとうたつかのうちょうてんへの最短距離さいたんきょりを計算けいさんする。無重むおもみグラフは $c = 1$ と解釈かいしゃくする。

4.2非負ひふの辺重へんおもみ

すべての辺へんについて $w (e) \geq 0$ である場合ばあい、ダイクストラ法ほうを適用てきようできる。この方法ほうほうは、暫定距離ざんていきょりが最小さいしょうの未確定頂点みかくていちょうてんを選択せんたくし、その頂点ちょうてんを経由けいゆする候補経路こうほけいろによって隣接頂点りんせつちょうてんの暫定距離ざんていきょりを更新こうしんする。非負性ひふせいにより、確定済かくていずみの距離きょりを後あとから短縮たんしゅくする経路けいろは存在そんざいしない。

4.3負辺ふへん

負辺ふへんnegative edgeとは $w (e) < 0$ である辺へんをいう。負辺ふへんが一辺いっぺんでも存在そんざいすると、未確定頂点みかくていちょうてんを暫定距離ざんていきょりだけで確定かくていするダイクストラ法ほうの論拠ろんきょは成立せいりつしない。ただし、負辺ふへんの存在そんざいだけでは最短路さいたんろの不存在ふそんざいを意味いみしない。負閉路ふへいろが関連かんれんしない場合ばあいは、Bellman--Ford法ほうなど負辺ふへんを許容きょようする方法ほうほうを使用しようできる。

data/lecture/information/algorithm/graph/dijkstra-algorithm-basics.lecture.n.md

5最適部分構造さいてきぶぶんこうぞう

$P = (v_{0}, \dots, v_{k})$ を $v_{0}$ から $v_{k}$ への最短路さいたんろとする。 $0 \leq i < j \leq k$ に対たいし、部分道ぶぶんどう $P [i : j] = (v_{i}, \dots, v_{j})$ も $v_{i}$ から $v_{j}$ への最短路さいたんろである。これを最短路さいたんろの最適部分構造さいてきぶぶんこうぞうoptimal substructureと呼よぶ。

実際じっさい、 $P [i : j]$ より費用ひようの小ちいさい歩道ほどう $Q$ が存在そんざいすると仮定かていする。 $P$ の当該部分とうがいぶぶんを $Q$ で置換ちかんすれば、 $v_{0}$ から $v_{k}$ への費用ひようが $P$ より小ちいさい歩道ほどうを構成こうせいでき、 $P$ の最短性さいたんせいに矛盾むじゅんする。したがって主張しゅちょうが成立せいりつする。この性質せいしつは、緩和かんわによって部分問題ぶぶんもんだいの最良値さいりょうちを結合けつごうする最短路さいたんろアルゴリズムの基礎きそとなる。

6まとめ

無向むこう・有向ゆうこうの別べつと、歩道ほどう・道みちの別べつを明示めいじしてから最短路問題さいたんろもんだいを定式化ていしきかする。
到達不能とうたつふのうなら距離きょりは $+ \infty$ であり、関連かんれんする負閉路ふへいろがあれば $- \infty$ である。
等重とうおもみではBFS、非負重ひふおもみではダイクストラ法ほうを適用てきようできる。負辺ふへんがある場合ばあいは別べつの方法ほうほうが必要ひつようである。
最短路さいたんろの任意にんいの部分道ぶぶんどうも、その両端りょうたんの間あいだの最短路さいたんろである。

Shortest-Path Basics

1Introduction

This lecture formulates shortest-path problems that minimize either the number of edges or the sum of edge weights. It then explains the applicability conditions for BFS, Dijkstra's algorithm, and methods that permit negative edges.

The lecture assumes the definitions of vertices, edges, walks, and paths, together with the layered structure of BFS.

data/lecture/information/graph/graph-basics.lecture.n.md data/lecture/information/algorithm/search/dfs-and-bfs-basics.lecture.n.md

2Graphs and routes

Let $G = (V, E)$ be a finite graph. An edge ${u, v}$ of an undirected graph has no orientation, whereas a directed edge $(u, v)$ permits movement only from $u$ to $v$ .

An $s$ -to- $t$ walk is a vertex sequence $v_{0} = s, v_{1}, \dots, v_{k} = t$ in which an edge of $E$ joins every pair of consecutive vertices. In a directed graph, each edge orientation must also agree with the sequence. A walk with no repeated vertex is a path. Its number of edges is $k$ .

An edge-weight function is a function $w : E \to R$ that assigns a real number to each edge. The cost of a walk $P = (v_{0}, \dots, v_{k})$ is

c (P) = \sum_{i = 1}^{k} w (v_{i - 1}, v_{i}) .

For an undirected edge, $w (v_{i - 1}, v_{i})$ denotes the weight of the undirected edge joining those two vertices. Minimizing the number of edges is equivalent to assigning weight $1$ to every edge.

3Distance and unreachability

Define the distance from $s$ to $t$ as the infimum of the costs of all $s$ -to- $t$ walks:

δ (s, t) = \inf {c (P) ∣ P isan s [PARSE ERROR: Undefined("RBrace")] t walk} .

If $t$ is unreachable from $s$ , the candidate set is empty, and we define $δ (s, t) = + \infty$ .

A closed walk is a walk whose first and last vertices coincide. A cycle is a closed walk with no repeated vertices other than its coincident endpoints. In a directed graph, every negative closed walk contains at least one negative cycle in its decomposition.

Suppose a negative cycle is reachable from $s$ and $t$ is reachable from that cycle. Repeating the cycle arbitrarily many times gives $δ (s, t) = - \infty$ , and no walk attains a minimum cost. In an undirected graph, traversing a negative edge in both directions forms a negative closed walk. Thus the distance is $- \infty$ whenever such an edge can occur on an $s$ -to- $t$ route.

Now suppose that no relevant negative cycle exists and that $t$ is reachable. If an arbitrary $s$ -to- $t$ walk repeats a vertex, the intervening closed subwalk has nonnegative cost and can be removed without increasing the cost. Repeating this operation produces a path. A finite graph has only finitely many $s$ -to- $t$ paths, so one of them attains the minimum cost. Such a path is called a shortest path from $s$ to $t$ .

4Choosing a method from the weights

4.1Equal edge weights

If all edge weights equal the same positive constant $c > 0$ , the cost is $c$ times the number of edges. Thus minimizing cost is equivalent to minimizing the number of edges. BFS processes vertices in nondecreasing order of their edge counts from the source, so it computes the shortest distance to every reachable vertex. An unweighted graph is interpreted as the case $c = 1$ .

4.2Nonnegative edge weights

If $w (e) \geq 0$ for every edge, Dijkstra's algorithm applies. It selects an unsettled vertex with minimum tentative distance and uses candidate routes through that vertex to update the tentative distances of adjacent vertices. Nonnegativity ensures that no later route can decrease a settled distance.

4.3Negative edges

A negative edge is an edge $e$ with $w (e) < 0$ . If even one negative edge exists, the justification for settling vertices solely by tentative distance in Dijkstra's algorithm no longer holds. A negative edge alone, however, does not imply that a shortest path fails to exist. If no relevant negative cycle exists, a method that permits negative edges, such as the Bellman--Ford algorithm, can be used.

data/lecture/information/algorithm/graph/dijkstra-algorithm-basics.lecture.n.md

5Optimal substructure

Let $P = (v_{0}, \dots, v_{k})$ be a shortest path from $v_{0}$ to $v_{k}$ . For every $0 \leq i < j \leq k$ , the subpath $P [i : j] = (v_{i}, \dots, v_{j})$ is also a shortest path from $v_{i}$ to $v_{j}$ . This property is called the optimal substructure of shortest paths.

Indeed, suppose that a walk $Q$ from $v_{i}$ to $v_{j}$ had lower cost than $P [i : j]$ . Replacing that portion of $P$ with $Q$ would construct a walk from $v_{0}$ to $v_{k}$ with lower cost than $P$ , contradicting the optimality of $P$ . The claim therefore holds. This property underlies shortest-path algorithms that combine optimal values of subproblems through relaxation.

6Summary

A shortest-path problem must specify whether the graph is directed or undirected and distinguish walks from paths.
The distance is $+ \infty$ when the target is unreachable and $- \infty$ when a relevant negative cycle exists.
BFS applies to equal weights, and Dijkstra's algorithm applies to nonnegative weights. Negative edges require a different method.
Every subpath of a shortest path is itself a shortest path between its endpoints.