<p><strong>Giải thuật Dijkstra (tìm đường đi ngắn nhất từ một đỉnh nguồn)</strong></p><p><strong>Dữ liệu:</strong></p><ul><li>Đồ thị có trọng số không âm G=(V,E)</li><li>Đỉnh nguồn s</li></ul><p><strong>Ý tưởng</strong></p><ul><li>Ban đầu: chỉ biết khoảng cách từ s đến chính nó</li><li>Mỗi bước chọn đỉnh có khoảng cách tạm thời nhỏ nhất</li><li>Cập nhật lại khoảng cách các đỉnh kề</li></ul><p><strong>Giải thuật:</strong></p><p>Bước 1:<br>   Khởi tạo:<br>       Với mỗi đỉnh u:<br>           dist[u] = vô cùng<br>           parent[u] = -1</p><p>       dist[s] = 0</p><p>Bước 2:<br>   Tạo một tập các đỉnh chưa xét (ban đầu gồm tất cả các đỉnh)</p><p>Bước 3:<br>   Lặp cho đến khi tập chưa xét rỗng:</p><p>       Chọn đỉnh u chưa xét sao cho dist[u] là nhỏ nhất</p><p>       Đánh dấu u là đã xét</p><p>       Với mỗi đỉnh v kề với u:<br>           Nếu v chưa xét và:<br>               dist[v] > dist[u] + trọng số(u, v) thì</p><p>               Cập nhật:<br>                   dist[v] = dist[u] + trọng số(u, v)<br>                   parent[v] = u</p><p>Bước 4:<br>   Sau khi kết thúc:<br>       dist[v] là độ dài đường đi ngắn nhất từ s đến v<br>       parent dùng để truy vết đường đi</p><p> </p><p><i><strong>***Muốn tìm đường đi từ s đến v:</strong></i></p><p>   Bắt đầu từ v:<br>       Lần lượt đi ngược qua parent[v]</p><p>   Dừng khi gặp s</p><p>   Đảo ngược lại để được đường đi đúng</p>