Skip to content

Instantly share code, notes, and snippets.

@kienmatu
Last active August 26, 2022 17:34
Show Gist options
  • Save kienmatu/b270064b353f077e621e79ff72feda4f to your computer and use it in GitHub Desktop.
Save kienmatu/b270064b353f077e621e79ff72feda4f to your computer and use it in GitHub Desktop.
Sample implementation of dijkstra by Java use OOP and priority queue
package com.kiendt;
import java.util.*;
public class Graph {
private static int INFINITY = 9999;
private int[][] matrix = {
{0, 10, 20, 9999, 9999, 9999},
{9999, 0, 9999, 50, 10, 9999},
{9999, 9999, 0, 20, 33, 9999},
{9999, 9999, 9999, 0, 20, 2},
{9999, 9999, 9999, 9999, 0, 1,},
{9999, 9999, 9999, 9999, 9999, 0}
};
public Graph() {
}
/**
* Tìm đường ngắn nhất từ start tới target
* Phương thức nhận 2 tham số
*
* @param startSymbol đỉnh bắt đầu
* @param targetSymbol đỉnh đích
*/
public void dijkstra(char startSymbol, char targetSymbol) {
List<Vertex> vertices = new ArrayList<>();
for (int i = 0; i < matrix.length; i++) {
Vertex vertex = new Vertex(i, i);
vertex.setDistance(INFINITY);
vertices.add(vertex);
}
Vertex startVertex = vertices.get(Vertex.getColFromSymbol(startSymbol));
Vertex targetVertex = vertices.get(Vertex.getColFromSymbol(targetSymbol));
startVertex.setDistance(0);
Queue<Vertex> vertexQueue = new PriorityQueue<>(Comparator.comparing(Vertex::getDistance));
vertexQueue.add(startVertex);
while (!vertexQueue.isEmpty()) {
Vertex current = vertexQueue.poll();
// xét đỉnh hàng xóm
for (Vertex neighbor : vertices) {
int nextWeight = matrix[current.getRow()][neighbor.getCol()];
// đỉnh hàng xóm tồn tại đường đi và khác đỉnh bắt đầu, tránh trường hợp quay ngược.
if (neighbor != startVertex && nextWeight != INFINITY) {
int distance = nextWeight + current.getDistance();
// chưa tồn tại đường đi
if (neighbor.getPrev() == null) {
neighbor.setDistance(distance);
neighbor.setPrev(current);
vertexQueue.add(neighbor);
}
// đường mới ngắn hơn đường cũ
else if (vertexQueue.contains(neighbor) && distance < neighbor.getDistance()) {
// lấy con đường mới ngắn hơn
neighbor.setDistance(distance);
neighbor.setPrev(current);
// cập nhật thứ tự ưu tiên
vertexQueue.remove(neighbor);
vertexQueue.add(neighbor);
}
}
if (neighbor == targetVertex) {
break;
}
}
}
if (targetVertex.getPrev() == null) {
System.out.println("KHÔNG TỒN TẠI ĐƯỜNG ĐI TỪ " + startSymbol + " TỚI " + targetSymbol);
} else {
System.out.println("ĐƯỜNG ĐI TỪ " + startSymbol + " TỚI " + targetSymbol + " MẤT " + targetVertex.getDistance());
printPath(startVertex, targetVertex);
}
}
/**
* In ra đường đi truy ngược theo prev
*
* @param startVertex đỉnh bắt đầu
* @param targetVertex đỉnh kết thúc
*/
private void printPath(Vertex startVertex, Vertex targetVertex) {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.insert(0, " -> " + targetVertex.getSymbol());
while (targetVertex.getPrev() != null) {
if (targetVertex == startVertex) {
break;
}
stringBuilder.insert(0, " -> " + targetVertex.getPrev().getSymbol());
targetVertex = targetVertex.getPrev();
}
System.out.println(stringBuilder.toString());
}
}
package com.kiendt;
public class Vertex {
private final static String ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
private int row;
private int col;
private int distance;
private Vertex prev;
public Vertex(int row, int col) {
this.row = row;
this.col = col;
}
public char getSymbol() {
return ALPHABET.charAt(col);
}
public static int getColFromSymbol(char symbol){
return ALPHABET.indexOf(symbol);
}
public int getRow() {
return row;
}
public void setRow(int row) {
this.row = row;
}
public int getCol() {
return col;
}
public void setCol(int col) {
this.col = col;
}
public int getDistance() {
return distance;
}
public void setDistance(int distance) {
this.distance = distance;
}
public Vertex getPrev() {
return prev;
}
public void setPrev(Vertex prev) {
this.prev = prev;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment