Дейкстра Алогритм дает неправильный кратчайший путь - PullRequest
Новая
       19

Дейкстра Алогритм дает неправильный кратчайший путь

0 голосов
/ 17 января 2019

Я преобразовал C++ реализацию Dijkstra's Algorithm в Java.Когда я запустил свой код Java, я не получил ожидаемый результат

Ожидаемый от моего кода C++: 

Minimum distance for source vertex 0 to reach vertex 0 is 0
Minimum distance for source vertex 0 to reach vertex 1 is 4
Minimum distance for source vertex 0 to reach vertex 2 is 12
Minimum distance for source vertex 0 to reach vertex 3 is 19
Minimum distance for source vertex 0 to reach vertex 4 is 21
Minimum distance for source vertex 0 to reach vertex 5 is 11
Minimum distance for source vertex 0 to reach vertex 6 is 9
Minimum distance for source vertex 0 to reach vertex 7 is 8
Minimum distance for source vertex 0 to reach vertex 8 is 14

Фактический от Java код: 

Minimum distance for source vertex 0 to reach vertex 0 is 0
Minimum distance for source vertex 0 to reach vertex 1 is 4
Minimum distance for source vertex 0 to reach vertex 2 is 2
Minimum distance for source vertex 0 to reach vertex 3 is 7
Minimum distance for source vertex 0 to reach vertex 4 is 9
Minimum distance for source vertex 0 to reach vertex 5 is 2
Minimum distance for source vertex 0 to reach vertex 6 is 1
Minimum distance for source vertex 0 to reach vertex 7 is 1
Minimum distance for source vertex 0 to reach vertex 8 is 2

Я пытался найти ошибку в своем Java-коде, я дважды проверил, правильно ли скопировал код C ++, я не нашел ничего другого.

Я уже трачу много времени на отладку своего кода.

Я не понимаю, что пошло не так!Я отчаянно нуждаюсь в помощи, спасибо!

Код: 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Dijkstra
{
    public static final int INF = 100000;

    private static class IPair implements Comparable<IPair>
    {
        int first;
        int second;

        IPair(int first, int second)
        {
            this.first = first;
            this.second = second;
        }

        public int compareTo(IPair that)
        {
            return this.first - that.first;
        }
    }

    public static int[] dijkstra(List<IPair>[] adj, int source)
    {
        Queue<IPair> pq = new PriorityQueue<>();
        int[] dist = new int[adj.length];
        boolean[] visited = new boolean[adj.length];

        Arrays.fill(dist, INF);

        pq.add(new IPair(0, source));
        dist[source] = 0;

        while (!pq.isEmpty())
        {
            int u = pq.poll().second;

            if (visited[u])
                continue;

            System.err.println(u);

            visited[u] = true;

            for (IPair pair : adj[u])
            {
                int v = pair.first;
                int weight = pair.second;

                if (dist[v] > dist[u] + weight)
                {
                    dist[v] = dist[u] + weight;
                    pq.add(new IPair(dist[v], v));

                    System.err.println(Arrays.toString(dist));
                }
            }
        }

        return dist;
    }

    private static void addEdge(List<IPair>[] adj, int u, int v, int weight)
    {
        adj[u].add(new IPair(v, weight));
        adj[v].add(new IPair(u, weight));
    }

    public static void main(String[] args)
    {
        int V = 9;

        List<IPair>[] adj = new ArrayList[V];

        Arrays.fill(adj, new ArrayList<IPair>());

        addEdge(adj, 0, 1, 4);
        addEdge(adj, 0, 7, 8);
        addEdge(adj, 1, 2, 8);
        addEdge(adj, 1, 7, 11);
        addEdge(adj, 2, 3, 7);
        addEdge(adj, 2, 8, 2);
        addEdge(adj, 2, 5, 4);
        addEdge(adj, 3, 4, 9);
        addEdge(adj, 3, 5, 14);
        addEdge(adj, 4, 5, 10);
        addEdge(adj, 5, 6, 2);
        addEdge(adj, 6, 7, 1);
        addEdge(adj, 6, 8, 6);
        addEdge(adj, 7, 8, 7);

        int[] dist = dijkstra(adj, 0);

        for (int i = 0; i < V; ++i)
            System.out.println("Minimum distance for source vertex " + 0 + " to reach vertex " + i + " is " + dist[i]);
    }
}

1 Ответ

0 голосов
/ 18 января 2019

Arrays.fill(adj, new ArrayList<IPair>())Эквивалентно:

List<IPair> list = new ArrayList<>();
Arrays.fill(adj, list)

Это означает, что вы сохраняете один и тот же List объект во всех элементах массива.Когда вы изменяете объект List на adj[x], он меняет объект List всех элементов adj, поскольку это один и тот же объект.Решение состоит в том, чтобы сохранить новый объект List в каждом элементе adj: 

//Arrays.fill(adj, new ArrayList<IPair>());
for (int i = 0; i < V; ++i) {
   adj[i] = new ArrayList<>();
}
...