Dijkstra for Adjacency matrix, Shortest and cheapest Path, single source, single target 邻接矩阵的Dijkstra

Question

我正在尝试实现 Dijkstra 算法以获得从一个顶点到另一个顶点的最短和成本最低的路径，而不是针对所有顶点。该图是通过使用随机权重连接的随机节点随机构建的。

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

迪杰斯特拉 - Class:

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);
}

}

图表 - Class 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 所有地方而不是 1 有边的地方和 Integer.MAX_VALUE 其他所有地方（实际上你应该在这种情况下使用 -1 并在您的代码中检查它。否则您的算法会说节点之间存在断开连接的路径。

4.这不是 Dijkstra

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

请参阅下方代码的固定版本。你应该尝试自己重新实现它，但既然我现在有了它......

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);
  }
}

Dijkstra for Adjacency matrix, Shortest and cheapest Path, single source, single target 邻接矩阵的Dijkstra

Dijsktra for Adjacency matrix, Shortest and cheapest Path, single source, single target

java

graph

dijkstra

path-finding

adjacency-matrix