Graph Algorithms Portal

date2026-07-14document_iddoc_abc7f7f63c0013b40ed92cbe0a46ed1cdescriptionグラフアルゴリズムの講義を、探索・到達可能性・最短路・ダイクストラ法の順に学習するための入口である。type講義statusactive

portalalgorithmgraphlecture

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.md

3.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.md

3.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.md

3.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.md

4Method-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