Giải thích các phương thức đã cài đặt trong code Dijkstra?

[sike]

em đang làm bài tập về thuật toán Dijkstras lên github tìm code thấy có code như này

public class Dijkstras {

	public static void main(String[] args) {
		Graph g = new Graph();
		g.addVertex('A', Arrays.asList(new Vertex('B', 7), new Vertex('C', 8)));
		g.addVertex('B', Arrays.asList(new Vertex('A', 7), new Vertex('F', 2)));
		g.addVertex('C', Arrays.asList(new Vertex('A', 8), new Vertex('F', 6), new Vertex('G', 4)));
		g.addVertex('D', Arrays.asList(new Vertex('F', 8)));
		g.addVertex('E', Arrays.asList(new Vertex('H', 1)));
		g.addVertex('F', Arrays.asList(new Vertex('B', 2), new Vertex('C', 6), new Vertex('D', 8), new Vertex('G', 9), new Vertex('H', 3)));
		g.addVertex('G', Arrays.asList(new Vertex('C', 4), new Vertex('F', 9)));
		g.addVertex('H', Arrays.asList(new Vertex('E', 1), new Vertex('F', 3)));
		System.out.println(g.getShortestPath('A', 'H'));
	}
	
}

class Vertex implements Comparable<Vertex> {
	
	private Character id;
	private Integer distance;
	
	public Vertex(Character id, Integer distance) {
		super();
		this.id = id;
		this.distance = distance;
	}

	public Character getId() {
		return id;
	}

	public Integer getDistance() {
		return distance;
	}

	public void setId(Character id) {
		this.id = id;
	}

	public void setDistance(Integer distance) {
		this.distance = distance;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result
				+ ((distance == null) ? 0 : distance.hashCode());
		result = prime * result + ((id == null) ? 0 : id.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Vertex other = (Vertex) obj;
		if (distance == null) {
			if (other.distance != null)
				return false;
		} else if (!distance.equals(other.distance))
			return false;
		if (id == null) {
			if (other.id != null)
				return false;
		} else if (!id.equals(other.id))
			return false;
		return true;
	}

	@Override
	public String toString() {
		return "Vertex [id=" + id + ", distance=" + distance + "]";
	}

	@Override
	public int compareTo(Vertex o) {
		if (this.distance < o.distance)
			return -1;
		else if (this.distance > o.distance)
			return 1;
		else
			return this.getId().compareTo(o.getId());
	}
	
}

class Graph {
	
	private final Map<Character, List<Vertex>> vertices;
	
	public Graph() {
		this.vertices = new HashMap<Character, List<Vertex>>();
	}
	
	public void addVertex(Character character, List<Vertex> vertex) {
		this.vertices.put(character, vertex);
	}
	
	public List<Character> getShortestPath(Character start, Character finish) {
		final Map<Character, Integer> distances = new HashMap<Character, Integer>();
		final Map<Character, Vertex> previous = new HashMap<Character, Vertex>();
		PriorityQueue<Vertex> nodes = new PriorityQueue<Vertex>();
		
		for(Character vertex : vertices.keySet()) {
			if (vertex == start) {
				distances.put(vertex, 0);
				nodes.add(new Vertex(vertex, 0));
			} else {
				distances.put(vertex, Integer.MAX_VALUE);
				nodes.add(new Vertex(vertex, Integer.MAX_VALUE));
			}
			previous.put(vertex, null);
		}
		
		while (!nodes.isEmpty()) {
			Vertex smallest = nodes.poll();
			if (smallest.getId() == finish) {
				final List<Character> path = new ArrayList<Character>();
				while (previous.get(smallest.getId()) != null) {
					path.add(smallest.getId());
					smallest = previous.get(smallest.getId());
				}
				return path;
			}

			if (distances.get(smallest.getId()) == Integer.MAX_VALUE) {
				break;
			}
						
			for (Vertex neighbor : vertices.get(smallest.getId())) {
				Integer alt = distances.get(smallest.getId()) + neighbor.getDistance();
				if (alt < distances.get(neighbor.getId())) {
					distances.put(neighbor.getId(), alt);
					previous.put(neighbor.getId(), smallest);
					
					forloop:
					for(Vertex n : nodes) {
						if (n.getId() == neighbor.getId()) {
							nodes.remove(n);
							n.setDistance(alt);
							nodes.add(n);
							break forloop;
						}
					}
				}
			}
		}
		
		return new ArrayList<Character>(distances.keySet());
	}
	
}

em có 1 số thắc mắc thế này :

1. tại sao phải cho class Vertex implements Comparable
2. tại sao phải implement các method hashcode() và equals() , trong khi interface chỉ cần implement method compareTo() thôi

về mặt thuật toán thì em đã hiểu vì đã làm trên giấy được nhưng đưa vào code thì chưa đang đi tham khảo có gì mấy anh giúp em với …

[PPly (Trong Hieu Nguyen)]

Tạo comparable cho Vertex để có thể so sánh 2 object type Vertex. Bạn có thể đọc thêm về Comparable trên mạng. Khi tạo comparable cho object thường phải override hashcode và equal (để định nghĩa như thế nào là 2 vertex equals và vì mỗi 1 object có 1 hashcode độc nhất nên cũng phải định nghĩa lại hashcode)

[sike]

nếu ko overide thì sẽ xảy ra chuyện gì ? về cái equals thì em hiểu vì 2 đối tượng mà dùng equals để so sánh thì sẽ so sánh giá trị ( vd : string dùng equals sẽ so sánh giá trị của 2 đối tượng string) , vậy còn hashcode có tác dụng gì không phải mối đối tượng trong java mặc định là đã được extend sẳn method hashcode rồi sao mình lại phải override lại ( chẳng nhẻ lại có trường hợp 2 đối tượng khác nhau mà lại cùng hashcode sao ??)

[tntxtnt]

có 2 đối tượng khác nhau nhưng cùng hashcode. Hashcode chỉ là 1 số nguyên 32-bit nên chỉ có 2³² giá trị, trong khi đối tượng là vô số, lớn hơn 2³² rất nhiều, đương nhiên là phải có trùng. Ví dụ thực tế Java String trùng rất nhiều. Đây là nguyên tắc pigeon hole chuồng chim bồ câu (3 con chim bồ câu 2 cái chuồng thì ít nhất 1 chuồng phải có 2 chim) ai cũng phải biết khi đụng tới hash :V

hashcode dùng trong hashmap hashset, Dijkstra ko liên quan mấy. Cụ thể hash map xài như mảng nhưng khác với mảng là truy cập theo đối tượng, còn mảng thì truy cập theo số nguyên. Ví dụ mảng là a[0], a[1], .v…, còn hash map thì m[“abc”], m[“xyz”], v.v… Em có thể hiểu hash map như mảng 2 chiều ko đồng đều :V, ví dụ m[8][?] trong đó dấu ? nghĩa là mảng m[i] có số phần tử chưa xác định. Để có thể truy cập theo đối tượng như vậy thì các đối tượng trong hash map cần phải được chuyển về 1 số nguyên, để m[“abc”] được máy nó hiểu là m[564165] rồi nó sẽ gán “abc” vào vị trí tương ứng cho số 564165, ví dụ là m[564165 % 8]. Nếu 2 đối tượng trùng hashcode thì m[564165 % 8] sẽ là mảng gồm 2 phần tử, và 2 phần tử này phân biệt với nhau bằng equals. Nếu equals cũng giống nhau thì 2 phần tử này là 1. Người ta thường dùng dslk thay cho mảng m[hashCode % m.size()] để tránh pointer invalidation :V

nếu em chỉ override equals mà ko override hashCode thì 2 đối tượng giống nhau có thể khác hashCode, dẫn tới khác vị trí a[hashCode % m.size()], dẫn tới m[“abc”] và m[s] với s = new MyString(“abc”) sẽ khác nhau. Nếu em override equals cho s và “abc” bằng nhau nhưng quên override hashCode thì m[“abc”] và m[s] khác nhau, vậy là ko sử dụng được hash map. Đương nhiên Dijkstra em ko sử dụng tới hash map thì ko vấn đề gì, nhưng theo thói quen thấy override equals mà ko override hashCode thì auto cho là code tầm bậy :V

[sike]

thanks anh cho em hỏi 1 câu nữa là ứng dụng thực tế của các thuật toán tìm đường đi ngắn nhất là gì , dĩ nhiên cái tên của nó cũng đã nói lên công dụng chính của nó là tìm đường đi nhưng ngoài việc tìm đường ra nó có thể tìm được cái gì nữa không ạ (vd dùng nó để giải quyết 1 số dạng vấn đề nào ko ạ )

[tntxtnt]

thấy gần đây có bài viết: https://blog.evjang.com/2018/08/dijkstras.html

dùng trong game nhiều với 1 dạng khác của Dijkstra là A*, ví dụ game Starcraft Warcraft gì mỗi lần click chuột tìm đường đi là mấy dạng tìm đường đi ngắn nhất này hết đó :V

hay mấy con robot hút bụi Roomba gì đó có thể có áp dụng Dijkstra vào được :V

có thể gu gồ maps cũng có áp dụng Dijkstra vào

à quên giải Sudoku xài DFS đó

trong image processing cũng có: https://en.wikipedia.org/wiki/Seam_carving là 1 dạng co hình ảnh ít làm biến dạng ảnh

bất cứ thứ gì có 1 trạng thái xác định, yêu cầu từ trạng thái này chuyển sang trạng thái khác hiệu quả nhất thì đều có thể chuyển về tìm đường đi ngắn nhất hết, vậy cho tỏng quát

[sike]

thanks anh , công nhận việc tìm ra giải thuật đã khó mà đưa nó vào code để giải quyết vấn đề cũng khó không kém , nhưng thành quả sau khi đạt được thì rất vui …