1. Gambaran keseluruhan
Penekanan dalam artikel ini adalah masalah jalan terpendek (SPP), menjadi salah satu masalah teori asas yang diketahui dalam teori grafik, dan bagaimana algoritma Dijkstra dapat digunakan untuk menyelesaikannya.
Matlamat asas algoritma adalah untuk menentukan jalan terpendek antara nod permulaan, dan graf yang selebihnya.
2. Masalah Laluan Terpendek Dengan Dijkstra
Memandangkan graf berwajaran positif dan simpul permulaan (A), Dijkstra menentukan jalan terpendek dan jarak dari sumber ke semua destinasi dalam grafik:
Idea teras algoritma Dijkstra adalah untuk secara berterusan menghilangkan jalan yang lebih panjang antara nod permulaan dan semua destinasi yang mungkin.
Untuk mengikuti prosesnya, kita perlu mempunyai dua set simpul yang berbeza, diselesaikan dan tidak tenteram.
Node yang diselesaikan adalah yang mempunyai jarak minimum yang diketahui dari sumbernya. Node yang tidak diselesaikan mengumpulkan node yang dapat kita jangkau dari sumbernya, tetapi kita tidak tahu jarak minimum dari simpul permulaan.
Berikut adalah senarai langkah yang perlu diikuti untuk menyelesaikan SPP dengan Dijkstra:
- Tetapkan jarak ke startNode ke sifar.
- Tetapkan semua jarak lain ke nilai yang tidak terhingga.
- Kami menambahkan startNode ke set nod yang tidak diselesaikan.
- Walaupun set nod yang tidak diselesaikan tidak kosong, kami:
- Pilih node penilaian dari set node yang tidak diselesaikan, node penilaian haruslah yang mempunyai jarak paling rendah dari sumber.
- Hitung jarak baru untuk mengarahkan jiran dengan menjaga jarak terendah pada setiap penilaian.
- Tambahkan jiran yang belum diselesaikan ke set nod yang belum selesai.
Langkah-langkah ini dapat digabungkan menjadi dua tahap, Permulaan dan Penilaian. Mari lihat bagaimana hal itu berlaku pada grafik sampel kami:
2.1. Permulaan
Sebelum kita mula meneroka semua jalan dalam grafik, pertama kita perlu menginisialisasi semua nod dengan jarak yang tidak terbatas dan pendahulunya yang tidak diketahui, kecuali sumbernya.
Sebagai sebahagian daripada proses inisialisasi, kita perlu menetapkan nilai 0 ke simpul A (kita tahu bahawa jarak dari simpul A ke nod A adalah 0 jelas)
Oleh itu, setiap nod di grafik yang lain akan dibezakan dengan pendahulunya dan jarak:
Untuk menyelesaikan proses inisialisasi, kita perlu menambahkan node A ke node yang tidak disetel agar dapat dipilih terlebih dahulu dalam langkah penilaian. Perlu diingat, set nod yang diselesaikan masih kosong.
2.2. Penilaian
Setelah grafik kita diinisialisasi, kita memilih simpul dengan jarak terendah dari set yang tidak diselesaikan, kemudian kita menilai semua nod bersebelahan yang tidak berada dalam nod yang diselesaikan:
Ideanya adalah untuk menambah berat tepi pada jarak simpul penilaian, kemudian membandingkannya dengan jarak tujuan. misalnya untuk nod B, 0 + 10 lebih rendah daripada INFINITY, jadi jarak baru untuk nod B adalah 10, dan pendahulunya yang baru adalah A, yang sama berlaku untuk nod C.
Node A kemudian dipindahkan dari node yang tidak disetel ke nod yang diselesaikan.
Node B dan C ditambahkan ke node yang tidak dapat diselesaikan kerana dapat dicapai, tetapi mereka perlu dinilai.
Sekarang kita mempunyai dua node dalam set yang tidak diselesaikan, kita memilih satu dengan jarak terendah (simpul B), kemudian kita mengulangi sehingga kita menyelesaikan semua nod dalam grafik:
Berikut adalah jadual yang merangkum lelaran yang dilakukan semasa langkah penilaian:
| Pengulangan | Tidak selesai | Menetap | Nod Penilaian | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|---|---|
| 1 | A | - | A | 0 | A-10 | A-15 | X-∞ | X-∞ | X-∞ |
| 2 | B, C | A | B | 0 | A-10 | A-15 | B-22 | X-∞ | B-25 |
| 3 | C, F, D | A, B | C | 0 | A-10 | A-15 | B-22 | C-25 | B-25 |
| 4 | D, E, F | A, B, C | D | 0 | A-10 | A-15 | B-22 | D-24 | D-23 |
| 5 | E, F | A, B, C, D | F | 0 | A-10 | A-15 | B-22 | D-24 | D-23 |
| 6 | E | A, B, C, D, F | E | 0 | A-10 | A-15 | B-22 | D-24 | D-23 |
| Akhir | - | SEMUA | TIADA | 0 | A-10 | A-15 | B-22 | D-24 | D-23 |
Sebagai contoh, notasi B-22 bermaksud bahawa simpul B adalah pendahulu terdekat, dengan jarak total 22 dari nod A.
Akhirnya, kita dapat mengira jalan terpendek dari nod A adalah seperti berikut:
- Node B: A -> B (jarak keseluruhan = 10)
- Node C: A -> C (jarak keseluruhan = 15)
- Node D: A -> B -> D (jarak keseluruhan = 22)
- Node E: A -> B -> D -> E (jarak keseluruhan = 24)
- Node F: A -> B -> D -> F (jarak keseluruhan = 23)
3. Pelaksanaan Java
Dalam pelaksanaan sederhana ini, kami akan mewakili grafik sebagai sekumpulan nod:
public class Graph { private Set nodes = new HashSet(); public void addNode(Node nodeA) { nodes.add(nodeA); } // getters and setters }A node can be described with a name, a LinkedList in reference to the shortestPath, a distance from the source, and an adjacency list named adjacentNodes:
public class Node { private String name; private List shortestPath = new LinkedList(); private Integer distance = Integer.MAX_VALUE; Map adjacentNodes = new HashMap(); public void addDestination(Node destination, int distance) { adjacentNodes.put(destination, distance); } public Node(String name) { this.name = name; } // getters and setters }The adjacentNodes attribute is used to associate immediate neighbors with edge length. This is a simplified implementation of an adjacency list, which is more suitable for the Dijkstra algorithm than the adjacency matrix.
As for the shortestPath attribute, it is a list of nodes that describes the shortest path calculated from the starting node.
By default, all node distances are initialized with Integer.MAX_VALUE to simulate an infinite distance as described in the initialization step.
Now, let's implement the Dijkstra algorithm:
public static Graph calculateShortestPathFromSource(Graph graph, Node source) { source.setDistance(0); Set settledNodes = new HashSet(); Set unsettledNodes = new HashSet(); unsettledNodes.add(source); while (unsettledNodes.size() != 0) { Node currentNode = getLowestDistanceNode(unsettledNodes); unsettledNodes.remove(currentNode); for (Entry adjacencyPair: currentNode.getAdjacentNodes().entrySet()) { Node adjacentNode = adjacencyPair.getKey(); Integer edgeWeight = adjacencyPair.getValue(); if (!settledNodes.contains(adjacentNode)) { calculateMinimumDistance(adjacentNode, edgeWeight, currentNode); unsettledNodes.add(adjacentNode); } } settledNodes.add(currentNode); } return graph; }The getLowestDistanceNode() method, returns the node with the lowest distance from the unsettled nodes set, while the calculateMinimumDistance() method compares the actual distance with the newly calculated one while following the newly explored path:
private static Node getLowestDistanceNode(Set unsettledNodes) { Node lowestDistanceNode = null; int lowestDistance = Integer.MAX_VALUE; for (Node node: unsettledNodes) { int nodeDistance = node.getDistance(); if (nodeDistance < lowestDistance) { lowestDistance = nodeDistance; lowestDistanceNode = node; } } return lowestDistanceNode; }private static void CalculateMinimumDistance(Node evaluationNode, Integer edgeWeigh, Node sourceNode) { Integer sourceDistance = sourceNode.getDistance(); if (sourceDistance + edgeWeigh < evaluationNode.getDistance()) { evaluationNode.setDistance(sourceDistance + edgeWeigh); LinkedList shortestPath = new LinkedList(sourceNode.getShortestPath()); shortestPath.add(sourceNode); evaluationNode.setShortestPath(shortestPath); } }Now that all the necessary pieces are in place, let's apply the Dijkstra algorithm on the sample graph being the subject of the article:
Node nodeA = new Node("A"); Node nodeB = new Node("B"); Node nodeC = new Node("C"); Node nodeD = new Node("D"); Node nodeE = new Node("E"); Node nodeF = new Node("F"); nodeA.addDestination(nodeB, 10); nodeA.addDestination(nodeC, 15); nodeB.addDestination(nodeD, 12); nodeB.addDestination(nodeF, 15); nodeC.addDestination(nodeE, 10); nodeD.addDestination(nodeE, 2); nodeD.addDestination(nodeF, 1); nodeF.addDestination(nodeE, 5); Graph graph = new Graph(); graph.addNode(nodeA); graph.addNode(nodeB); graph.addNode(nodeC); graph.addNode(nodeD); graph.addNode(nodeE); graph.addNode(nodeF); graph = Dijkstra.calculateShortestPathFromSource(graph, nodeA); Setelah pengiraan, atribut jalan terpendek dan jarak ditetapkan untuk setiap simpul dalam grafik, kita dapat melakukan lelaran untuk mengesahkan bahawa hasilnya sesuai dengan apa yang dijumpai di bahagian sebelumnya.
4. Kesimpulan
Dalam artikel ini, kita telah melihat bagaimana algoritma Dijkstra menyelesaikan SPP, dan bagaimana menerapkannya di Java.
Pelaksanaan projek sederhana ini boleh didapati di pautan projek GitHub berikut.