1. ภาพรวม
สิ่งที่เน้นในบทความนี้คือปัญหาเส้นทางที่สั้นที่สุด (SPP) ซึ่งเป็นหนึ่งในปัญหาทางทฤษฎีพื้นฐานที่รู้จักกันในทฤษฎีกราฟและวิธีที่สามารถใช้อัลกอริทึม Dijkstra เพื่อแก้ปัญหาได้
เป้าหมายพื้นฐานของอัลกอริทึมคือการกำหนดเส้นทางที่สั้นที่สุดระหว่างโหนดเริ่มต้นและส่วนที่เหลือของกราฟ
2. ปัญหาเส้นทางที่สั้นที่สุดกับ Dijkstra
ด้วยกราฟที่ถ่วงน้ำหนักในเชิงบวกและโหนดเริ่มต้น (A) Dijkstra จะกำหนดเส้นทางและระยะทางที่สั้นที่สุดจากต้นทางไปยังปลายทางทั้งหมดในกราฟ:
แนวคิดหลักของอัลกอริทึม Dijkstra คือการกำจัดเส้นทางที่ยาวขึ้นอย่างต่อเนื่องระหว่างโหนดเริ่มต้นและปลายทางที่เป็นไปได้ทั้งหมด
ในการติดตามกระบวนการเราจำเป็นต้องมีชุดโหนดที่แตกต่างกันสองชุดตัดสินและยกเลิกการตั้งค่า
โหนดที่ถูกตัดสินคือโหนดที่มีระยะทางต่ำสุดที่ทราบจากแหล่งที่มา ชุดโหนดที่ไม่มั่นคงจะรวบรวมโหนดที่เราสามารถเข้าถึงได้จากต้นทาง แต่เราไม่ทราบระยะทางต่ำสุดจากโหนดเริ่มต้น
นี่คือรายการขั้นตอนที่ต้องปฏิบัติตามเพื่อแก้ปัญหา SPP ด้วย Dijkstra:
- ตั้งค่าระยะทางให้startNodeเป็นศูนย์
- ตั้งค่าระยะทางอื่น ๆ ทั้งหมดเป็นค่าอนันต์
- เราเพิ่มstartNodeไปยังชุดโหนดที่ไม่ได้ตั้งค่า
- แม้ว่าชุดโหนดที่ไม่ได้ตั้งค่าจะไม่ว่างเปล่าเรา:
- เลือกโหนดการประเมินจากชุดโหนดที่ไม่ได้ตั้งค่าโหนดการประเมินควรเป็นโหนดที่มีระยะทางต่ำสุดจากต้นทาง
- คำนวณระยะทางใหม่เพื่อนำทางเพื่อนบ้านโดยรักษาระยะทางที่ต่ำที่สุดในการประเมินแต่ละครั้ง
- เพิ่มเพื่อนบ้านที่ยังไม่ได้ตั้งค่าให้กับชุดโหนดที่ไม่ได้ตั้งค่า
ขั้นตอนเหล่านี้สามารถรวมเป็นสองขั้นตอนการเริ่มต้นและการประเมินผล มาดูกันว่ามันใช้กับกราฟตัวอย่างของเราอย่างไร:
2.1. การเริ่มต้น
ก่อนที่เราจะเริ่มสำรวจเส้นทางทั้งหมดในกราฟก่อนอื่นเราต้องเริ่มต้นโหนดทั้งหมดด้วยระยะทางที่ไม่สิ้นสุดและรุ่นก่อนที่ไม่รู้จักยกเว้นแหล่งที่มา
ในกระบวนการเริ่มต้นเราจำเป็นต้องกำหนดค่า 0 ให้กับโหนด A (เรารู้ว่าระยะห่างจากโหนด A ถึงโหนด A คือ 0 อย่างชัดเจน)
ดังนั้นแต่ละโหนดในส่วนที่เหลือของกราฟจะมีความโดดเด่นด้วยรุ่นก่อนและระยะทาง:
ในการสิ้นสุดขั้นตอนการเริ่มต้นเราต้องเพิ่มโหนด A ในโหนดที่ไม่ได้ตั้งค่าซึ่งตั้งค่าให้ถูกเลือกก่อนในขั้นตอนการประเมิน โปรดทราบว่าชุดโหนดที่ชำระแล้วยังคงว่างเปล่า
2.2. การประเมินผล
ตอนนี้เราได้เริ่มต้นกราฟแล้วเราเลือกโหนดที่มีระยะทางต่ำสุดจากชุดที่ไม่ได้กำหนดจากนั้นเราจะประเมินโหนดที่อยู่ติดกันทั้งหมดที่ไม่ได้อยู่ในโหนดที่ถูกตัดสิน:
แนวคิดคือการเพิ่มน้ำหนักขอบให้กับระยะโหนดการประเมินจากนั้นเปรียบเทียบกับระยะทางของปลายทาง เช่นสำหรับโหนด B 0 + 10 ต่ำกว่า INFINITY ดังนั้นระยะห่างใหม่สำหรับโหนด B คือ 10 และรุ่นก่อนหน้าใหม่คือ A เช่นเดียวกับโหนด C
จากนั้นโหนด A จะถูกย้ายจากโหนดที่ไม่ได้ตั้งค่าไปยังโหนดที่กำหนด
โหนด B และ C ถูกเพิ่มลงในโหนดที่ไม่ได้ตั้งค่าเนื่องจากสามารถเข้าถึงได้ แต่จำเป็นต้องได้รับการประเมิน
ตอนนี้เรามีสองโหนดในชุดที่ยังไม่เรียบร้อยเราเลือกอันที่มีระยะทางต่ำสุด (โหนด B) จากนั้นเราจะย้ำจนกว่าเราจะกำหนดโหนดทั้งหมดในกราฟ:
นี่คือตารางสรุปการทำซ้ำที่ดำเนินการระหว่างขั้นตอนการประเมิน:
| การทำซ้ำ | ไม่มั่นคง | ตัดสิน | EvaluationNode | ก | ข | ค | ง | จ | ฉ |
|---|---|---|---|---|---|---|---|---|---|
| 1 | ก | - | ก | 0 | A-10 | ก -15 | X-∞ | X-∞ | X-∞ |
| 2 | B, C | ก | ข | 0 | A-10 | ก -15 | B-22 | X-∞ | B-25 |
| 3 | C, F, D | ก, ข | ค | 0 | A-10 | ก -15 | B-22 | ค -25 | B-25 |
| 4 | D, E, F | A, B, C | ง | 0 | A-10 | ก -15 | B-22 | D-24 | D-23 |
| 5 | E, F | เอบีซีดี | ฉ | 0 | A-10 | ก -15 | B-22 | D-24 | D-23 |
| 6 | จ | A, B, C, D, F | จ | 0 | A-10 | ก -15 | B-22 | D-24 | D-23 |
| สุดท้าย | - | ทั้งหมด | ไม่มี | 0 | A-10 | ก -15 | B-22 | D-24 | D-23 |
ตัวอย่างเช่นสัญกรณ์ B-22 หมายความว่าโหนด B เป็นรุ่นก่อนหน้าโดยมีระยะทางรวม 22 จากโหนด A
สุดท้ายเราสามารถคำนวณเส้นทางที่สั้นที่สุดจากโหนด A ได้ดังนี้:
- โหนด B: A -> B (ระยะทางรวม = 10)
- โหนด C: A -> C (ระยะทางรวม = 15)
- โหนด D: A -> B -> D (ระยะทางรวม = 22)
- โหนด E: A -> B -> D -> E (ระยะทางรวม = 24)
- โหนด F: A -> B -> D -> F (ระยะทางรวม = 23)
3. การใช้งาน Java
ในการใช้งานอย่างง่ายนี้เราจะแสดงกราฟเป็นชุดของโหนด:
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); หลังจากการคำนวณแอตทริบิวต์shortestPathและdistanceจะถูกตั้งค่าสำหรับแต่ละโหนดในกราฟเราสามารถวนซ้ำเพื่อตรวจสอบว่าผลลัพธ์ตรงกับสิ่งที่พบในส่วนก่อนหน้า
4. สรุป
ในบทความนี้เราได้เห็นวิธีที่อัลกอริทึม Dijkstra แก้ SPP และวิธีการนำไปใช้ใน Java
การดำเนินการของโครงการง่ายๆนี้สามารถพบได้ในลิงค์โครงการ GitHub ต่อไปนี้