16 Aug Lý thuyết đồ thị – Thuật toán Dijsktra
Cho một đồ thị G = (V, E) với:
– V là tập các đỉnh của đồ thị
– E là tập các cạnh của đồ thị sao cho trọng số các cung d(E) đều > 0.
– và một đỉnh cố định s nằm trong V.
Tìm đường ngắn nhất từ đỉnh s đến mỗi đỉnh v trong V.
– V là tập các đỉnh của đồ thị
– E là tập các cạnh của đồ thị sao cho trọng số các cung d(E) đều > 0.
– và một đỉnh cố định s nằm trong V.
Tìm đường ngắn nhất từ đỉnh s đến mỗi đỉnh v trong V.
Đồ thị trên có thể được biểu diễn bằng một ma trận 2 chiều m[r,c] sao cho mỗi giá trị m[r,c] là trọng số của cung nối đỉnh r và đỉnh c. Nếu không tồn tại cung nối giữa 2 đỉnh, giá trị này bằng 0. Bạn sẽ hiểu rõ hơn trong phần định nghĩa map của mã nguồn.
Thuật toán Dijkstra’s
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
1. Khởi tạo tập đỉnh Q = {} 2. Với mỗi đỉnh v trong V: dist[v] = infinity // tập chứa khoảng cách gần nhất tới mỗi đỉnh prev[v] = undefined // tập chứa đỉnh liền kề với một đỉnh, dùng để tìm đường đưa v vào Q 3. dist[s] = 0 // khoảng cách đến đỉnh xuất phát được set là 0 4. Lặp nếu Q chưa rỗng: tìm u sao cho dist[u] min gỡ u ra khỏi Q Lặp với mỗi v là đỉnh kề của u: alt = dist[u] + length(u, v) // tính khoảng cách đến v theo con đường đi qua u nếu alt < dist[v]: // nếu là khoảng cách ngắn hơn dist[v] = alt // update khoảng cách mới prev[v] = u // set đỉnh u là đỉnh kề của v 5. return dist[], prev[] |
Mã nguồn thuật toán:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
class Program { static int[,] _map = new int[,] { { 0, 3, 0, 0, 0, 0, 0, 0}, { 3, 0, 5, 2, 0, 0, 0, 0}, { 0, 5, 0, 2, 1, 0, 0, 0}, { 0, 2, 2, 0, 0, 3, 0, 0}, { 0, 0, 1, 0, 0, 1, 4, 0}, { 0, 0, 0, 3, 1, 0, 2, 0}, { 0, 0, 0, 0, 4, 2, 0, 3}, { 0, 0, 0, 0, 0, 0, 3, 0} }; static void Main(string[] args) { var numV = _map.GetLength(0); var dist = new int[numV]; var prev = new int[numV]; var d = ShortestPath(0, _map, ref dist, ref prev); Console.Read(); } static int FindMinU(List<int> Q, int[] dist) { var minU = 1000000; var u = Q[0]; for (int i = 0; i < Q.Count; i++) { if (minU > dist[Q[i]]) { minU = dist[Q[i]]; u = Q[i]; } } return u; } static int[] ShortestPath(int source, int[,] map, ref int[] dist, ref int[] prev) { var Q = new List<int>(); var numV = map.GetLength(0); for (int i = 0; i < map.GetLength(0); i++) { dist[i] = 1000000; prev[i] = -1; Q.Add(i); } dist[source] = 0; while (Q.Count() > 0) { var u = FindMinU(Q, dist); Q.Remove(u); for (int v = 0; v < numV; v++) { if (map[u, v] > 0) { var alt = dist[u] + map[u, v]; if (alt < dist[v]) { dist[v] = alt; prev[v] = u; } } } } return dist; } } |
No Comments