Алгоритм Дейкстры Java, ошибка пути при использовании нескольких источников

Question

Я нашел Алгоритм Дейкстры из Интернета (здесь оригинальный код), и я пытаюсь использовать несколько источников вместо нескольких мест назначения. Но когда я запускаю код, вывод не правильный, он просто показывает первую вершину для всего вывода.

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Vertex implements Comparable<Vertex> {

    public final String name;
    public Edge[] adjacencies;
    public double minDistance = Double.POSITIVE_INFINITY;
    public Vertex previous;
    public Vertex(String argName) { name = argName; }
    public String toString() { return name; }
    public int compareTo(Vertex other) {
        return Double.compare(minDistance, other.minDistance);
    }

}

class Edge {

    public final Vertex target;
    public final double weight;

    public Edge(Vertex argTarget, double argWeight) {
        target = argTarget;
        weight = argWeight;
    }

}

public class tes_dijkstra {

    public static void computePaths(Vertex source) {
        source.minDistance = 0.;
        PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
        vertexQueue.add(source);

        while (!vertexQueue.isEmpty()) {
            Vertex u = vertexQueue.poll();
            // Visit each edge exiting u
            for (Edge e : u.adjacencies) {
                Vertex v = e.target;
                double weight = e.weight;
                double distanceThroughU = u.minDistance + weight;
                if (distanceThroughU < v.minDistance) {
                    vertexQueue.remove(v);
                    v.minDistance = distanceThroughU ;
                    v.previous = u;
                    vertexQueue.add(v);
                }
            }
        }
    }

    public static List<Vertex> getShortestPathTo(Vertex target) {
        List<Vertex> path = new ArrayList<Vertex>();
        for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
            path.add(vertex);
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        Vertex v0 = new Vertex("Redvile");
        Vertex v1 = new Vertex("Blueville");
        Vertex v2 = new Vertex("Greenville");
        Vertex v3 = new Vertex("Orangeville");
        Vertex v4 = new Vertex("Purpleville");

        v0.adjacencies = new Edge[]{ new Edge(v1, 5),
                                     new Edge(v2, 10),
                                     new Edge(v3, 8) };
        v1.adjacencies = new Edge[]{ new Edge(v0, 5),
                                     new Edge(v2, 3),
                                     new Edge(v4, 7) };
        v2.adjacencies = new Edge[]{ new Edge(v0, 10),
                                     new Edge(v1, 3) };
        v3.adjacencies = new Edge[]{ new Edge(v0, 8),
                                     new Edge(v4, 2) };
        v4.adjacencies = new Edge[]{ new Edge(v1, 7),
                                 new Edge(v3, 2) };
        Vertex[] start = { v1, v2, v3, v4 };
        Vertex[] end ={v2};

        for (int i = 0; i < start.length; i++){
            for(int j = 0; j < end.length; j++){
                computePaths(start[i]);
                System.out.println("Distance to " + end[j] + ": " + end[j].minDistance);
                List<Vertex> path = getShortestPathTo(end[j]);
                System.out.println("Path: " + path);
            }
        }
    }
}

и вот как выглядит результат:

Distance to Greenville: 3.0
Path: [Blueville, Greenville]
Distance to Greenville: 0.0
Path: [Blueville, Greenville]
Distance to Greenville: 0.0
Path: [Blueville, Greenville]
Distance to Greenville: 0.0
Path: [Blueville, Greenville]

Выходные данные просто показывают первую вершину из начала Vertex[] (v1 = Blueville) для всех выходных данных. Я не знаю, где не так, где-то хранится путь? Я немного новичок в Java, и я хочу изучить этот алгоритм для моего задания, поэтому, пожалуйста, помогите. Спасибо

Answer 1

Да, вершины хранят информацию о стоимости и построенном пути. Проблема не столько в том, что сам путь построен, а в minDistance это расстояние от заданной начальной вершины. Вы можете реализовать метод reset в Vertex учебный класс

void reset () {
    this.minDistance = Double.POSITIVE_INFINITY;
}

И, кроме того, вам нужно сбросить все вершины графа, когда вы хотите выполнить следующий алгоритм Дейкстры:

public static List<Vertex> getShortestPathTo(Vertex target) {
    List<Vertex> path = new ArrayList<Vertex>();
    for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
        path.add(vertex);
    Collections.reverse(path);
    return path;
}

public static void main(String[] args) {
    Vertex v0 = new Vertex("Redvile");
    Vertex v1 = new Vertex("Blueville");
    Vertex v2 = new Vertex("Greenville");
    Vertex v3 = new Vertex("Orangeville");
    Vertex v4 = new Vertex("Purpleville");

    v0.adjacencies = new Edge[]{ new Edge(v1, 5),
                                 new Edge(v2, 10),
                                 new Edge(v3, 8) };
    v1.adjacencies = new Edge[]{ new Edge(v0, 5),
                                 new Edge(v2, 3),
                                 new Edge(v4, 7) };
    v2.adjacencies = new Edge[]{ new Edge(v0, 10),
                                 new Edge(v1, 3) };
    v3.adjacencies = new Edge[]{ new Edge(v0, 8),
                                 new Edge(v4, 2) };
    v4.adjacencies = new Edge[]{ new Edge(v1, 7),
                             new Edge(v3, 2) };
    Vertex[] start = { v1, v2, v3, v4 };
    Vertex[] end = {v2};
    Vertex[] all = {v0, v1, v2, v3, v4};

    for (int i = 0; i < start.length; i++){
        for(int j = 0; j < end.length; j++){
            computePaths(start[i]);
            System.out.println("Distance to " + end[j] + ": " + end[j].minDistance);
            List<Vertex> path = getShortestPathTo(end[j]);
            System.out.println("Path: " + path);
        }
        //a new start vertex: reset the graph
        for(Vertex v : all) {
            v.reset();
        }
    }
}