Dijkstra算法辅助

给定一个邻接矩阵，我需要计算第一个顶点和最后一个顶点之间的最短路径（通常是顶点i和j，但我们暂时可以忽略）。我写了一个算法，它只能正确地计算第一个和第二个节点之间的距离（我猜是朝着正确的方向迈出了一步）。Dijkstra算法辅助

static int dijkstra(int[][] G, int i, int j) { 
    //Get the number of vertices in G 
    int n = G.length; 
    int[] bestpath = new int[n]; 
    int max = Integer.MAX_VALUE; 
    boolean[] visited = new boolean[n]; 

    for (int x = 0; x < n; x++) { 
     visited[x] = false; 
     bestpath[x] = max; 
    } 

    bestpath[i] = 0; 

    for (int x = 0; x < n; x++) { 
     int min = max; 
     int currentNode = i; 
     for (int y = 0; y < n; y++) { 
      if (!visited[y] && bestpath[y] < min) { 
       System.out.println(G[y][x]); 
       currentNode = y; 
       min = bestpath[y]; 
      } 
     } 
     visited[currentNode] = true; 
     for (int y = 0; y < n; y++) { 
      if (G[currentNode][y] < max && bestpath[currentNode] + G[currentNode][y] < bestpath[y]) { 
       bestpath[y] = bestpath[currentNode] + G[currentNode][y]; 
      } 
     } 
    } 

    return bestpath[j]; 
}

如果我猜的话，我会说我的逻辑是在本节有缺陷：

for (int y = 0; y < n; y++) { 
      if (!visited[y] && bestpath[y] < min) { 
       System.out.println(G[y][x]); 
       currentNode = y; 
       min = bestpath[y]; 
      } 
}

一个例子是矩阵

0 1 0 
1 0 1 
0 1 0

这将返回2（重量1的顶点1和2之间的一条路径以及重量1的2和3之间的一条路径）。

来源

2012-12-03 Tyler Sebastian

如果矩阵不只是存储1s和0s，而是存储从i到j的距离，那么您确实需要跟踪从任何节点i到j的最佳距离。换句话说，你的工作阵列应该是一个工作矩阵。即使你只是做一个非加权图，我认为这种方法更好。

有不同版本的SPF算法。为你想要翻译成java的文章发布伪代码。

来源

2012-12-03 02:52:51 Thorn

Dijkstra算法辅助

回答

相关问题