Thuật toán Dijkstra
Tags:
AI
Algorithm
Pathfinding
C# Code
// Giả mã cho thuật toán Dijkstra.
// Khác với A*, Dijkstra không sử dụng chi phí ước tính (heuristic),
// nó khám phá tất cả các hướng một cách đồng đều.
public void Dijkstra(Graph graph, Node source) {
Dictionary<Node, int> dist = new Dictionary<Node, int>();
Dictionary<Node, Node> prev = new Dictionary<Node, Node>();
List<Node> unvisited = new List<Node>();
foreach (Node v in graph.Vertices) {
dist[v] = int.MaxValue;
prev[v] = null;
unvisited.Add(v);
}
dist[source] = 0;
while (unvisited.Count > 0) {
// Tìm node có khoảng cách nhỏ nhất trong danh sách chưa thăm
Node u = unvisited.OrderBy(node => dist[node]).First();
unvisited.Remove(u);
foreach (Node v in GetNeighbours(u)) {
int alt = dist[u] + GetWeight(u, v);
if (alt < dist[v]) {
dist[v] = alt;
prev[v] = u;
}
}
}
// Kết quả: dist chứa khoảng cách ngắn nhất từ source đến mọi node.
}Thuật toán Dijkstra tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong một đồ thị có trọng số không âm. Hữu ích cho việc tính toán phạm vi di chuyển.