Để triển khai thuật toán tìm đường đi ngắn nhất Dijkstra, trước hết - chúng ta phải tạo các cạnh và đỉnh của biểu đồ:
File Vert.java
package dijkstra.algo;
import java.util.ArrayList;
import java.util.List;
public class Vert implements Comparable<Vert> {
private boolean visited;
private String name;
private List<Edge> List;
private double dist = Double.MAX_VALUE;
private Vert pr;
public Vert(String name) {
this.name = name;
this.List = new ArrayList<>();
}
public List<Edge> getList() {
return List;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public void setList(List<Edge> List) {
this.List = List;
}
public void addNeighbour(Edge edge) {
this.List.add(edge);
}
public boolean Visited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
public Vert getPr() {
return pr;
}
public void setPr(Vert pr) {
this.pr = pr;
}
public double getDist() {
return dist;
}
public void setDist(double dist) {
this.dist = dist;
}
@Override
public String toString() {
return this.name;
}
@Override
public int compareTo(Vert otherV) {
return Double.compare(this.dist, otherV.getDist());
}
}
File Edge.java
package dijkstra.algo;
public class Edge {
private double weight;
private Vert startVert;
private Vert targetVert;
public Edge(double weight, Vert startVert, Vert targetVert) {
this.weight = weight;
this.startVert = startVert;
this.targetVert = targetVert;
}
public double getWeight() {
return weight;
}
public void setWeight(double weight) {
this.weight = weight;
}
public Vert getStartVert() {
return startVert;
}
public void setStartVert(Vert startVert) {
this.startVert = startVert;
}
public Vert getTargetVert() {
return targetVert;
}
public void setTargetVert(Vert targetVert) {
this.targetVert = targetVert;
}
}
File PathFinder.java
package dijkstra.algo;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
public class PathFinder {
public void ShortestP(Vert sourceV) {
sourceV.setDist(0);
PriorityQueue<Vert> priorityQueue = new PriorityQueue<>();
priorityQueue.add(sourceV);
sourceV.setVisited(true);
while (!priorityQueue.isEmpty()) {
Vert actualVertex = priorityQueue.poll();
for (Edge edge : actualVertex.getList()) {
Vert v = edge.getTargetVert();
if (!v.Visited()) {
double newDistance = actualVertex.getDist()
+ edge.getWeight();
if (newDistance < v.getDist()) {
priorityQueue.remove(v);
v.setDist(newDistance);
v.setPr(actualVertex);
priorityQueue.add(v);
}
}
}
actualVertex.setVisited(true);
}
}
public List<Vert> getShortestP(Vert targetVertex) {
List<Vert> path = new ArrayList<>();
for (Vert vertex = targetVertex; vertex != null; vertex = vertex.getPr()) {
path.add(vertex);
}
Collections.reverse(path);
return path;
}
}
File Dijkstra.java
package dijkstra.algo;
public class Dijkstra {
public static void main(String[] args) {
Vert vA = new Vert("A");
Vert vB = new Vert("B");
Vert vC = new Vert("C");
Vert vD = new Vert("D");
Vert vE = new Vert("E");
vA.addNeighbour(new Edge(3, vA, vC));
vA.addNeighbour(new Edge(5, vA, vB));
vC.addNeighbour(new Edge(2, vC, vB));
vC.addNeighbour(new Edge(6, vC, vE));
vC.addNeighbour(new Edge(5, vC, vD));
vB.addNeighbour(new Edge(4, vB, vC));
vB.addNeighbour(new Edge(3, vB, vD));
vB.addNeighbour(new Edge(4, vB, vE));
vE.addNeighbour(new Edge(2, vE, vD));
PathFinder shortestPath = new PathFinder();
shortestPath.ShortestP(vA);
System.out.println("Khoảng cách tối thiểu từ:");
System.out.println("A đến B: " + vB.getDist());
System.out.println("A đến C: " + vC.getDist());
System.out.println("A đến D: " + vD.getDist());
System.out.println("A đến E: " + vE.getDist());
System.out.println("Đường đi ngắn nhất từ:");
System.out.println("A đến B: " + shortestPath.getShortestP(vB));
System.out.println("A đến C: " + shortestPath.getShortestP(vC));
System.out.println("A đến D: " + shortestPath.getShortestP(vD));
System.out.println("A đến E: " + shortestPath.getShortestP(vE));
}
}
Khi chạy chương trình, kết quả ta nhận được là:
Khoảng cách tối thiểu từ:
A đến B: 5.0
A đến C: 3.0
A đến D: 8.0
A đến E: 9.0
Đương đingắn nhất từ:
A đến B: [A, B]
A đến C: [A, C]
A đến D: [A, C, D]
A đến E: [A, C, E]
Dijkstra là thuật toán tìm đường đi có thể nói là đơn giản nhất.
Trong đồ thị, còn nhiều giải thuật tìm đường đi khác, tuỳ vào trường hợp và mục đích sử dụng mà bạn có thể dành thời gian tìm hiểu để nâng cao trình độ của mình như:
Giải bài toán đường đi ngắn nhất nguồn đơn (simple-source): Ta sẽ tìm đường đi ngắn nhất từ đỉnh nguồn v đến tất cả các đỉnh khác. Có 2 thuật toán quan trọng: Thuật toán Dijkstra (Đối với trọng số dương) và Thuật toán Bellman-Ford (Đối với trọng số bất kỳ).
Giải bài toán đường đi ngắn nhất nguồn đích (simple-destination): Ta sẽ tìm đường đi ngắn nhất trong đồ thị có hướng từ các đỉnh đến đỉnh đích v. Ta có thể giải quyết bằng cách đảo ngược hướng của đồ thị và trở thành bài toán nguồn đơn.
Giải bài toán đường đi ngắn nhất cho mọi cặp đỉnh: Ta sẽ tìm đường đi ngắn nhất giữa 2 đỉnh bất kỳ. Có 2 thuật toán quan trọng: Thuật toán Floyd-Warshall và Thuật toán Johnson.
Như vậy, qua bài hướng dẫn này bạn đã tìm hiểu được một cách để giải bài toán tìm đường đi ngắn nhất (Shortest path).
Đến đây, bạn cũng đã được học về các thuật toán Bubble sort, Selection sort, Insertion sort, Quick sort, Merge sort, Heap sort, Binary search và cả Shortest path nữa.
Cũng đã kha khá để bạn có một nền tảng thuật toán cơ bản rồi đó.
Hãy tự luyện tập thêm để thực sự hiểu rõ và vận dụng được những thuật toán này trong các tình huống khác nhau bạn nhé.
> Đừng quên, nếu bạn muốn chinh phục ngôn ngữ Java, đặc biệt là Java Web thì đừng bỏ qua KHÓA HỌC JAVA (Full Stack) của NIIT - ICT Hà Nội nhé.
> Hoặc, nếu bạn chưa có nền tảng về lập trình mà muốn học đầy đủ hơn thì KHÓA HỌC LẬP TRÌNH VIÊN FULL STACK sẽ giúp bạn trở thành lập trình viên vững vàng trong vòng 12 tháng.
---
HỌC VIỆN ĐÀO TẠO CNTT NIIT - ICT HÀ NỘI
Học Lập trình chất lượng cao (Since 2002). Học làm Lập trình viên. Hành động ngay!
Đc: Tầng 3, 25T2, N05, Nguyễn Thị Thập, Cầu Giấy, Hà Nội
SĐT: 02435574074 - 0914939543
Email: hello@niithanoi.edu.vn
Fanpage: https://facebook.com/NIIT.ICT/
#niit #niithanoi #niiticthanoi #hoclaptrinh #khoahoclaptrinh #hoclaptrinhjava #hoclaptrinhphp #java #php #python