Thuật toán tìm đường đi ngắn nhất Dijkstra

Threads: Algorithms

1. Bài toán

Cho đồ thị vô hướng có trọng số G(N,M) với N đỉnh và M cạnh. Tìm đường đi ngắn nhất từ đỉnh S đến đỉnh E.

Input: 
- Dòng đầu là số N,M (n<10^3)
- Dòng tiếp theo là 2 đỉnh S, E
- M dòng tiếp theo là 3 số u v w với  u, v là 2 đỉnh, w là trọng số chi phí

Output
- Dòng đầu là chi phí MIN từ S đến E
- Dòng tiếp theo là đường đi từ S đến E

Ví dụ minh họa

Iniput:
6 7
1 4
1 2 4
1 6 20
2 3 2
3 4 20
3 6 3
4 5 5
5 6 1

Output
15
1 2 3 6 5 4

Please login or register to see more...

Tags: Thuật toán tìm đường đi ngắn nhất Dijkstra

Reviews

Please login or register to comment