使用DFS和堆栈的未加权图中的最短路径

Question

我是java编程的新手，我试图用DFS方法和堆栈来编写一个可以在未加权图中找到最短路径的程序。我期待着一个递归DFS方法，可以找到两个节点之间的短路径。我不知道如何实现DFS搜索帮助，这是我的代码。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;
import javax.swing.JOptionPane;
public class pruebaGrafosinpesos {
public static void main(String[] args) {
// TODO Auto-generated method stub
int opcion=0, i=0, origen=0, destino=0, contador=0, n=-1;
boolean[] visitados= new boolean[10];//arreglo que indica los nodos visitados
Stack<Integer> camino= new Stack();//stack que guarda el camino recorrido
Stack<Integer> temp= new Stack();//stack que guarda el camino recorrido
LinkedList<Integer>[] nodo = new LinkedList[10];//arreglo de las conexiones de cada nodo
for(i=0; i<10; i++) {
nodo[i]= new LinkedList<Integer>();
}
for(i=0; i<10; i++) {
visitados[i]=false;
}
//inicializo el grafo
nodo[0].add(1); nodo[0].add(2);
nodo[1].add(0); nodo[1].add(2); nodo[1].add(3);
nodo[2].add(1); nodo[2].add(5); nodo[2].add(6);
nodo[3].add(1); nodo[3].add(4); nodo[3].add(7);
nodo[4].add(3); nodo[4].add(5); nodo[4].add(7);
nodo[5].add(2); nodo[5].add(4); nodo[5].add(6); nodo[5].add(8);
nodo[6].add(2); nodo[6].add(5); nodo[6].add(8);
nodo[7].add(3); nodo[7].add(4); nodo[7].add(8);
nodo[8].add(4); nodo[8].add(5); nodo[8].add(6); nodo[8].add(9);
nodo[9].add(7); nodo[9].add(8);
///////////////// Matriz //////////////////////
/*|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | / | * | * |   |   |   |   |   |   |   |
| 1 | * | / | * | * |   |   |   |   |   |   |
| 2 |   | * | / |   |   | * | * |   |   |   |
| 3 |   | * |   | / | * |   |   | * |   |   |
| 4 |   |   |   | * | / | * |   | * |   |   |
| 5 |   |   | * |   | * | / | * |   | * |   |
| 6 |   |   | * |   |   | * | / |   | * |   |
| 7 |   |   |   | * | * |   |   | / | * |   |
| 8 |   |   |   |   | * | * | * |   | / | * |
| 9 |   |   |   |   |   |   |   | * | * | / |*/
///////////////////////////////////////////////
do {
opcion=Integer.parseInt(JOptionPane.showInputDialog("1.-Encontrar el camino mas corton 2.-Salirn Escoge una opcion"));
switch(opcion) {
case 1:
origen=Integer.parseInt(JOptionPane.showInputDialog("Dame el nodo origen"));
destino=Integer.parseInt(JOptionPane.showInputDialog("Dame el nodo destino"));
n=origen;
while(contador<=10) {
if(visitados[n]==false) {//si el nodo no ha sido visitado
visitados[n]=true;//se visita
camino.push(n);//se agrega al stack del camino recorrido
contador++;
}


}
break;
case 2:
break;
}
}while(opcion!=2);
}

}

Answer 1

如果您乐于使用递归方法，那么您真的不需要堆栈变量。您只需要一个字段来存储迄今为止找到的最短路径

我可以在这里提供一些伪代码供您转换为Java

shortest = null
dfs({start})
dfs(path):
if end of path is destination
if shortest is null or path is shorter than shortest
shortest = path
else
for each node reachable from end of path
if node not in path
dfs(path + node)

该算法将对整个图执行DFS，并找到从起点到终点节点的最短路径。您也可以让它返回最短路径，而不是将其存储为搜索的副作用。

---

为了您的兴趣，这里有一个使用稍微不同的数据结构的解决方案。路径本质上充当堆栈。

public class Network {
private final List<Node> nodes;
private class Node {
private final List<Node> links = new ArrayList<>();
}
public class Path {
private final Optional<Path> previous;
private final Node end;
private Path(Optional<Path> previous, Node node) {
this.previous = previous;
this.end = node;
}
public String toString() {
return nodes().map(n -> Integer.toString(nodes.indexOf(n))).collect(Collectors.joining(", "));
}
private Stream<Node> nodes() {
return Stream.concat(previous.stream().flatMap(Path::nodes), Stream.of(end));
}
}
public Network(int nodeCount) {
this.nodes = IntStream.range(0, nodeCount).mapToObj(i -> new Node()).collect(Collectors.toList());
}
public void linkNodes(int from, int to) {
assert from != to : "link to self";
getNode(from).links.add(getNode(to));
getNode(to).links.add(getNode(from));
}
public Optional<Path> shortest(int from, int to) {
return shortest(new Path(Optional.empty(), getNode(from)), getNode(to));
}
private Optional<Path> shortest(Path path, Node to) {
if (path.end.equals(to))
return Optional.of(path);
else
return path.end.links.stream()
.filter(ln -> path.nodes().noneMatch(ln::equals))
.flatMap(ln -> shortest(new Path(Optional.of(path), ln), to).stream())
.min(Comparator.comparingLong(p -> p.nodes().count()));
}
private Node getNode(int id) {
assert id >= 0 && id < nodes.size(): "illegal node id";
return nodes.get(id);
}
}