Алгоритм Дейкстры на Java

[@UUU-y8t]

Все: Полезное видио и вопросы по теме
Я: Матрица смежности для 3.14doorов
Ну а если вежливо и без тупых шуток с моей стороны то пожалуйста дайте ответ на вопрос: зачем городить классы вершин и дуг если матрица смежности неплохо описывает граф нам ведь памяти не на миллион вершин нужно выделить так что потратить O(n^2) или O((n^2)/2) в случае неорентированного графа можно благо памяти не 64 килобайта как в рассказах моего научного руководителя.

[@onnikorpela282]

public class App {
public static void main(String[] args) {
System.out.println("Hello world!");
Vertex A = new Vertex("A");
Vertex B = new Vertex("B");
Vertex C = new Vertex("C");
Vertex D = new Vertex("D");
Vertex E = new Vertex("E");
Vertex F = new Vertex("F");
Vertex G = new Vertex("G");
Vertex H = new Vertex("H");
A.addNeighbor(new Edge(5, A, B));
A.addNeighbor(new Edge(9, A, E));
B.addNeighbor(new Edge(4, B, H));
B.addNeighbor(new Edge(12, B, C));
B.addNeighbor(new Edge(15, B, D));
C.addNeighbor(new Edge(3, C, D));
C.addNeighbor(new Edge(11, C, G));
D.addNeighbor(new Edge(9, D, G));
E.addNeighbor(new Edge(5, E, H));
E.addNeighbor(new Edge(4, E, F));
E.addNeighbor(new Edge(20, E, G));
F.addNeighbor(new Edge(1, F, C));
F.addNeighbor(new Edge(13, F, G));
H.addNeighbor(new Edge(7, H, C));
H.addNeighbor(new Edge(6, H, E));
Dijkstra dijkstra = new Dijkstra();
dijkstra.compute(A);
System.out.println(G.getDistance());
dijkstra.showPath(G);
}
}
//------------------------------------------
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
public class Dijkstra {
PriorityQueue queue;
public Dijkstra() {
queue = new PriorityQueue();
}
public void compute(Vertex sourse){
sourse.setDistance(0);
queue.add(sourse);
while (!queue.isEmpty()){
Vertex curr = queue.poll();
for (Edge e: curr.getNeighbours()){
Vertex end = e.getEnd();
double w = e.getWeight();
if (!end.isVisited()){
if (curr.getDistance() + w < end.getDistance()){
end.setDistance(curr.getDistance()+w);
if (queue.contains(end))
queue.remove(end);
queue.add(end);
end.setPredecrssor(curr);
}
}
}
curr.setVisited(true);
}
}
public void showPath(Vertex end){
List path = new ArrayList();
while (end != null){
// System.out.print(end.getName());
path.add(end);
end = end.getPredecrssor();
}
Collections.reverse(path);
for (Vertex v: path)
System.out.print(v.getName() + " " );
}
}
public class Edge {
Vertex start;
Vertex end;
double weight;
public Edge(double weight, Vertex start, Vertex end) {
this.start = start;
this.end = end;
this.weight = weight;
}
public Vertex getStart() {
return start;
}
public void setStart(Vertex start) {
this.start = start;
}
public Vertex getEnd() {
return end;
}
public void setEnd(Vertex end) {
this.end = end;
}
public double getWeight() {
return weight;
}
public void setWeight(double weight) {
this.weight = weight;
}
}
import java.util.ArrayList;
import java.util.List;
public class Vertex implements Comparable {
String name;
boolean visited;
List neighbours;
double distance;
Vertex predecrssor;
public Vertex(String name) {
this.name = name;
neighbours = new ArrayList();
distance = Double.MAX_VALUE;
predecrssor = null;
}
public Vertex getPredecrssor() {
return predecrssor;
}
public void setPredecrssor(Vertex predecrssor) {
this.predecrssor = predecrssor;
}
public double getDistance() {
return distance;
}
public void setDistance(double distance) {
this.distance = distance;
}
public void addNeighbor(Edge edge) {
neighbours.add(edge);
}
public String getName() {
return name;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
public List getNeighbours() {
return neighbours;
}
@Override
public int compareTo(Vertex o1) {
return Double.compare(this.getDistance(), o1.getDistance());
}
}

[@АлександрБугримов-о1е]

Полезное видео. Спасибо большое

[@volodymyrKarpyshyn]

15:52, чтоб не вставлять в каждый "neigbour" - 'h' отдельно, можно зажать ALT и, зажав левую кнопку мыши, провести курсор вниз или вверх. Это даст возможность писать текст сразу в нескольких строках

[@homofaber1002]

Большое спасибо.

[@John.Constantine.777]

удалять ссылку на узел в очереди, а потом ее же добавлять?
а че, так можно было?.. .))

[@ՀայկԱրտինյան-խ5փ]

kak xorosho chto ti ne zabrosil yutube