java - Dijkstra 用于邻接矩阵、最短且最便宜的路径、单一源、单一目标

Question

我正在尝试实现 Dijkstra 算法，以便获得从一个顶点到另一个顶点的最短且最便宜的路径，而不是所有顶点。该图是使用与随机权重连接的随机节点随机构建的。

但是要么我得到负成本，要么两种方法(最便宜和最短)的路径是相同的。我试图使用相同的方法找到这两个结果，因为最短路径只是忽略权重。这是由 boolean 变量控制的。

Dijkstra - 类别:

public class Dijkstra {

private Graph graph;
private int[] distance;
private boolean[] visited;
private int[] parents;
private int startNode;
private int endNode;

public Dijkstra(Graph graph, int startNode, int endNode) {
    this.graph = graph;
    distance = new int[graph.getAdjList().length];
    visited = new boolean[graph.getAdjList().length];
    parents = new int[graph.getAdjList().length];
    this.startNode = startNode;
    this.endNode = endNode;
}

public void findPath(boolean isUnweighted) {
    if (endNode == startNode) {
        System.out.println(
                "Starting node  " + startNode + "  and target node " + endNode + " are identical.");
        return;
    }
    System.out.println("Starting node: " + startNode);
    System.out.println("Target node:  " + endNode);
    int[][] adjList = graph.getAdjList();
    int[][] graphForPathFinding = new int[adjList.length][adjList.length];

    if (isUnweighted) {
        // set all weights to 1
        graphForPathFinding = convertGraphToUnweighted(graphForPathFinding);
    } else
        graphForPathFinding = adjList;
    // initialize
    for (int i = 0; i < adjList.length; i++) {
        parents[i] = Integer.MAX_VALUE;
        visited[i] = false;
        distance[i] = Integer.MAX_VALUE;
    }

    distance[startNode] = 0;
    for (int i = 0; i < graphForPathFinding.length; i++) {

        int nextNode = getMinDistance();
        if (nextNode == -1) { // no path found
            System.out.println(
                    "No path found between " + startNode + " and " + endNode);
            return;
        }
        visited[nextNode] = true;
        parents[i] = nextNode;

        if (nextNode == endNode) {
            printResults();
            return; // target node reached
        }
        int[] neighbors = graph.getNeighbors(nextNode);
        for (int j = 0; j < neighbors.length; j++) {

             if (!visited[j] && neighbors[j] > 0 && distance[nextNode] !=
             Integer.MAX_VALUE
             && distance[nextNode] + neighbors[j] < distance[j])
             distance[j] = distance[nextNode] + neighbors[j];
        }

    }

}

private int getMinDistance() {
    int min = Integer.MAX_VALUE;
    int min_index = -1;

    for (int i = 0; i < graph.getAdjList().length; i++) {
        if (visited[i] == false && distance[i] <= min) {
            min = distance[i];
            min_index = i;
        }

    }
    return min_index;
}

private int[][] convertGraphToUnweighted(int[][] graphForConverting) {
    for (int i = 0; i < graph.getAdjList().length; i++) {
        for (int j = 0; j < graph.getAdjList()[i].length; j++) {
             //if (graph.getAdjList()[i][j] > 0) {
            graphForConverting[i][j] = 1;
        // }
        }
    }
    return graphForConverting;
}

private void printResults() {
int weight = 0;
int steps = 0;
System.out.println("Pfad: ");
    for(int i = endNode; i>=0; i--){
        if(parents[i] < Integer.MAX_VALUE){
            System.out.print(parents[i] + "    ");
            steps++;
            weight += graph.getAdjList()[i][parents[i]];
        }

    }

    System.out.println();
    System.out.println("Number of nodes: " + steps);
     System.out.println("Weight:  " + weight);
}

}

图 - getNeighbors 类

public int[] getNeighbors(int node){
        int neighborCount = 0;
        for(int i = 0; i < adjList[node].length; ++i)
            if(adjList[node][i] > 0)
                ++neighborCount;
        int[] neighbours = new int[neighborCount];
        neighborCount = 0;
        for(int i = 0; i < adjList[node].length; ++i)
            if(adjList[node][i] > 0)
                neighbours[neighborCount++] = i;

        return neighbours;
    }

主要方法:

 public static void main(String[] args) {
            int startNode = rnd.nextInt(graph.getAdjList().length);
            int endNode = rnd.nextInt(graph.getAdjList().length);
            Dijkstra d = new Dijkstra(graph, startNode, endNode);

            System.out.println("Shortest path:");
            d.findPath(true); // true = unweighted, false = weighted
            System.out.println();
            System.out.println("Cheapest path:");
            d.findPath(false);
}

Answer 1

好吧，我花了一段时间才弄清楚你的算法被破坏的原因和方式，因为有很多问题:

<强>1。 getMinDistance() 错误

在这种方法中，您尝试找到接下来要访问的最便宜的节点，这是正确的想法，但实现是错误的。首先，您要考虑图中的所有节点，而不仅仅是您当前正在访问的节点的邻居，其次，您使用 distance 数组来查找成本。但其中所有未访问节点的值为 Integer.MAX_VALUE，因此该方法将始终选择索引最高的节点。

<强>2。您使用了错误的邻接列表

对于最短路径，您将创建原始邻接列表的修改副本，但随后您不会使用它。

<强>3。您修改后的邻接列表错误

创建最短路径的修改副本时，您可以将所有位置的值设置为 1，而不是有边缘和 Integer.MAX_VALUE 的位置的 1 code> 对于其他所有内容(实际上，在这种情况下您应该使用 -1 并在代码中检查它。否则您的算法会说断开连接的节点之间存在路径)。

<强>4。这不是 Dijkstra

我花了一段时间才发现这一点，因为有时你会得到正确的结果，但这不是 Dijkstra's Algorithm 。为了正确实现它，您需要一个优先级队列或其他一些机制来跟踪距离并获得最小值。您尝试使用“getMinDistance”方法，但这种方法是错误的，因为您考虑了图中的所有节点，而不仅仅是“队列中”的节点。

请参阅下面的代码的固定版本。你应该尝试自己重新实现它，但无论如何我现在已经有了它......

public class Dijkstra {

  private static final class DijkstraComparator implements Comparator<Integer> {
    private final int[] distance;

    DijkstraComparator(int[] distance) {
        this.distance = distance;
    }

    @Override
    public int compare(Integer o1, Integer o2) {
        return Integer.compare(distance[o1], distance[o2]);
    }
  }

  private Graph graph;
  private int[] distance;
  private boolean[] visited;
  private int[] parents;
  private int startNode;
  private int endNode;

  public Dijkstra(Graph graph, int startNode, int endNode) {
    this.graph = graph;
    distance = new int[graph.getAdjList().length];
    visited = new boolean[graph.getAdjList().length];
    parents = new int[graph.getAdjList().length];
    this.startNode = startNode;
    this.endNode = endNode;
  }

  public void findPath(boolean isUnweighted) {
    if (endNode == startNode) {
        System.out.println("Starting node  " + startNode + "  and target node " + endNode + " are identical.");
        return;
    }

    int[][] graphForPathFinding;
    if (isUnweighted) {
        // set all weights to 1
        graphForPathFinding = convertGraphToUnweighted();
    } else {
        graphForPathFinding = graph.getAdjList();
    }

    // initialize
    for (int i = 0; i < parents.length; i++) {
        parents[i] = Integer.MAX_VALUE;
        visited[i] = false;
        distance[i] = Integer.MAX_VALUE;
    }

    PriorityQueue<Integer> queue = new PriorityQueue<>(1, new DijkstraComparator(distance));
    distance[startNode] = 0;
    queue.add(startNode);

    while (queue.isEmpty() == false) {
        int nextNode = queue.poll();
        visited[nextNode] = true;

        if (nextNode == endNode) {
            printResults();
            return; // target node reached
        }

        int[] neighbors = graph.getNeighbors(nextNode);
        for (int neighbor : neighbors) {
            if (visited[neighbor] == false) {
                // update distance
                int d = distance[nextNode] + graphForPathFinding[nextNode][neighbor];
                if (d < distance[neighbor]) {
                    distance[neighbor] = d;
                    parents[neighbor] = nextNode;

                    // remove neighbors from queue so the value gets updated
                    if (queue.contains(neighbor)) {
                        queue.remove(neighbor);
                    }
                    queue.add(neighbor);
                }
            }
        }
    }
    System.out.println("No path found between " + startNode + " and " + endNode);
  }

  private int[][] convertGraphToUnweighted() {
    int[][] adjMatrix = graph.getAdjList();
    int[][] graphForConverting = new int[adjMatrix.length][adjMatrix.length];
    for (int i = 0; i < adjMatrix.length; i++) {
        int[] adjList = adjMatrix[i];
        for (int j = 0; j < adjList.length; j++) {
            if (adjList[j] != 0) {
                graphForConverting[i][j] = 1;
            } else {
                graphForConverting[i][j] = Integer.MAX_VALUE;
            }
        }
    }
    return graphForConverting;
  }

  private void printResults() {
    int weight = 0;
    int steps = 0;
    System.out.println("Pfad: ");
    for (int node = endNode; node != startNode; steps++) {
        System.out.print(node + "    ");
        weight += graph.getAdjList()[parents[node]][node];
        node = parents[node];
    }
    System.out.println(startNode);
    System.out.println("Number of nodes: " + steps);
    System.out.println("Weight:  " + weight);
  }
}