java - Dijkstra 算法自身的实现问题
问题描述
我在一个简单的 Graph 类中有这个 Dijkstra 算法 O(n^2) 实现,在调试它时,输出与 JUnit 测试的预期不同,我找不到问题:
public void Dijkstra(T departureNode) {
initDijkstra(departureNode);
ArrayList<GraphNode<T>> V_S = fillWithoutElement(departureNode);
while (V_S.size() > 0) {
int w = chooseMinimum(D);
nodes.get(w).setVisited(true);
GraphNode<T> auxW = nodes.get(w);
V_S.remove(findOnV_S(V_S, auxW));
for(GraphNode<T> m : V_S) {
if (D[w] + weights[w][getNode(m.getElement())] < D[getNode(m.getElement())]) {
D[getNode(m.getElement())] = D[w] + weights[w][getNode(m.getElement())];
PD[getNode(m.getElement())] = w;
}
}
}
}
这是辅助方法chooseMinimum():
private int chooseMinimum(double[] auxD) {
int res = 0;
double min = INFINITE;
for (int i = 0; i < auxD.length; i++) {
if (!nodes.get(i).isVisited()) {
if (auxD[i] < min) {
min = auxD[i];
res = i;
}
}
}
return res;
}
这是 findOnV_S() 方法:
private int findOnV_S(ArrayList<GraphNode<T>> V_S, GraphNode<T> auxW) {
int res = 0;
for(int i = 0; i < V_S.size(); i++) {
if(V_S.get(i).equals(auxW))
res = i;
}
return res;
}
这是 initDijkstra() 方法:
public void initDijkstra(T departureNode) {
if (!itExists(departureNode))
throw new IllegalArgumentException("Node does not exist");
D = new double[size];
PD = new int[size];
int j = getNode(departureNode);
// Initialize D
for (int i = 0; i < size; i++) {
if (edges[j][i]) {
D[i] = weights[j][i];
} else
D[i] = INFINITE;
}
// Initialize PD
for (int i = 0; i < size; i++) {
if (edges[j][i])
PD[i] = getNode(departureNode);
else
PD[i] = EMPTY;
}
initializeVisitedToFalseExceptStart(departureNode);
}
这是 initializeVisitedToFalseExceptStart 辅助方法:
private void initializeVisitedToFalseExceptStart(T departureNode) {
if (!itExists(departureNode))
throw new RuntimeException("Invalid node");
GraphNode<T> element = null;
for (int i = 0; i < size; i++) {
element = nodes.get(i);
if ((element.getElement()).equals(departureNode))
element.setVisited(true);
else
nodes.get(i).setVisited(false);
}
}
PD:我认为错误的方法是chooseMinimum()
PD2:在下一个 JUnit 中,您将看到 getD() 将返回一个二维数组,但 Graph 类中的实际 D 是一个一维数组。
PD3:这是简单的 JUnit 测试:
try
{
g.addNode("V1");
g.addNode("V2");
g.addNode("V3");
g.addNode("V4");
g.addNode("V5");
g.addNode("V6");
}
catch (Exception e)
{
System.out.println ("No repeated nodes are allowed" + e);
}
try
{
g.addEdge ("V1", "V2", 3.0);
g.addEdge ("V1", "V3", 4.0);
g.addEdge ("V1", "V5", 8.0);
g.addEdge ("V2", "V5", 5.0);
g.addEdge ("V3", "V5", 3.0);
g.addEdge ("V5", "V6", 3.0);
g.addEdge ("V5", "V4", 7.0);
g.addEdge ("V6", "V4", 2.0);
}
catch (Exception e)
{
System.out.println ("Starting or arrival node does not exists" + e);
}
g.Dijkstra ("V1");
assertArrayEquals (new double[][]{{Graph.INFINITE, 3.0, 4.0, 12.0, 7.0, 10.0}}, g.getD());
assertArrayEquals (new int[]{-1, 0, 0, 5, 2, 4}, g.getPD());
解决方案
我想我找到了问题所在。您在 initDijkstra 方法中有一个名为 initializeVisitedToFalseExceptStart(departureNode) 的方法。因此,当在 while 循环中完成对 chooseMinimum 的初始调用时,您会在不考虑离开节点的情况下找到最小值
我认为如果您将在 initDijkstra 方法中删除该方法调用,您的算法将运行良好。
推荐阅读
- selenium - 我在 Capturescreensot 方法和自定义侦听器中收到“java.lang.NullPointerException”
- azure - 有没有办法使用 Graph API 获取管理员同意请求列表?
- javascript - 如何在javascript中将变量修剪并保存到字符串中的第一个空格
- python - 未检测到 Python 3.8 安装
- laravel - 如何获取特定型号的视频?
- php - 从网页中提取版本信息的查询
- c++ - a.exe:文件无法识别:文件被截断
- java - 春季启动查询,这有什么问题?
- jquery - 将fancybox 1 迁移到fancybox 3
- kotlin - 我们可以使用 Kotlin 接口实现类似 Rust 的 Traits