グラフアルゴリズムポータル
1導入
このポータルでは、グラフの
グラフアルゴリズムでは、まず
2学習目標
無重 みグラフと重 み付 きグラフの相違 を説明 できる。到達可能性 の判定 と最短路 の計算 を区別 できる。無重 み最短路 にはBFSを、非負 の重 みをもつ最短路 にはダイクストラ法 を選択 できる。各手法 の前提条件 を確認 し、適用範囲 を説明 できる。
3学習順序
3.11. グラフの基本
3.22. DFSとBFS
DFSとBFSによる
3.33. 最短路問題
3.44. ダイクストラ法
4手法選択 の基準
| DFSまたはBFS | ||
| BFS | ||
| ダイクストラ | ||
| ダイクストラ |
Graph Algorithms Portal
1Introduction
This portal explains the learning sequence from graph fundamentals through traversal and shortest-path problems to Dijkstra's algorithm.
Graph algorithms begin by defining vertices, edges, adjacency, paths, and distance. DFS and BFS then determine reachability, and the BFS lecture establishes why BFS computes shortest distances in an unweighted graph. The shortest-path lecture subsequently formulates problems involving edge weights, and the final lecture presents Dijkstra's algorithm for the case in which all weights are nonnegative.
2Learning objectives
- Explain the distinction between unweighted and weighted graphs.
- Distinguish reachability testing from shortest-path computation.
- Select BFS for unweighted shortest paths and Dijkstra's algorithm for shortest paths with nonnegative weights.
- Identify the assumptions of each method and explain its domain of applicability.
3Learning sequence
3.11. Graph fundamentals
Review vertices, edges, adjacency, paths, and distance, which form the common language of traversal and shortest paths.
data/lecture/information/graph/graph-basics.lecture.n.md3.22. DFS and BFS
Study how DFS and BFS determine reachability. For BFS, also establish shortest-path correctness when every edge has the same cost, as in an unweighted graph.
data/lecture/information/algorithm/search/dfs-and-bfs-basics.lecture.n.md3.33. Shortest-path problems
Distinguish measuring path length by the number of edges from measuring it by the sum of edge weights. This distinction determines whether BFS or a weighted shortest-path algorithm is applicable.
data/lecture/information/algorithm/graph/shortest-path-basics.lecture.n.md3.44. Dijkstra's algorithm
Under the assumption that every edge weight is nonnegative, study the principle by which Dijkstra's algorithm finalizes tentative distances. The method is not applicable to graphs containing negative edge weights.
data/lecture/information/algorithm/graph/dijkstra-algorithm-basics.lecture.n.md4Method-selection criteria
| Problem condition | Objective | Basic method |
|---|---|---|
| Weights are not considered | Determine reachability | DFS or BFS |
| Every edge has the same positive cost | Minimize the number of edges | BFS |
| Edges have possibly different nonnegative weights | Minimize the sum of weights | Dijkstra's algorithm |
| Some edge has a negative weight | Minimize the sum of weights | Outside the domain of Dijkstra's algorithm |