Кратчайший путь (наименьшее количество узлов) для невзвешенного графика
При изменении конфигурационного файла веб-сайта ASP.NET он перезапускает приложение для отражения изменений...
, Когда Вы делаете Сброс IIS, который перезапускает все приложения, работающие на том экземпляре IIS.
4 ответа
На самом деле ваш код не завершится в циклических графах, рассмотрим граф 1 -> 2 -> 1. У вас должен быть некоторый массив, в котором вы можете отметить, какие узлы вы уже посетили. А также для каждого узла вы можете сохранить предыдущие узлы, с которых вы пришли. Итак, вот правильный код:
private Map<Node, Boolean>> vis = new HashMap<Node, Boolean>();
private Map<Node, Node> prev = new HashMap<Node, Node>();
public List getDirections(Node start, Node finish){
List directions = new LinkedList();
Queue q = new LinkedList();
Node current = start;
q.add(current);
vis.put(current, true);
while(!q.isEmpty()){
current = q.remove();
if (current.equals(finish)){
break;
}else{
for(Node node : current.getOutNodes()){
if(!vis.contains(node)){
q.add(node);
vis.put(node, true);
prev.put(node, current);
}
}
}
}
if (!current.equals(finish)){
System.out.println("can't reach destination");
}
for(Node node = finish; node != null; node = prev.get(node)) {
directions.add(node);
}
directions.reverse();
return directions;
}
На самом деле получить ответ для одной пары не проще, чем для всех пар. Обычный способ вычисления кратчайшего пути - это начать так же, как и вы, но делать пометки всякий раз, когда вы встречаетесь с новым узлом, и записывать предыдущий узел на пути. Затем, когда вы достигнете целевого узла, вы можете перейти по обратным ссылкам на источник и получить путь. Итак, удалите direction.add (current) из цикла и добавьте примерно такой код
Map<Node,Node> backlinks = new HashMap<Node,Node>();
вначале, затем в цикл
if (!backlinks.containsKey(node)) {
backlinks.add(node, current);
q.add(node);
}
, а затем в конце просто создайте направлений перечислить в обратном направлении с помощью карты обратных ссылок .
Каждый раз во время цикла вы вызываете
directions.Add(current);
Вместо этого вы должны переместить эту в место, где вы действительно знаете, что хотите эту запись.
Вы должны включить родительский узел для каждого узла, когда вы помещаете их в свою очередь. Затем вы можете просто рекурсивно прочитать путь из этого списка.
Допустим, вы хотите найти кратчайший путь от A до D на этом графике:
/B------C------D
/ |
A /
\ /
\E---------
Каждый раз, когда вы ставите узел в очередь, отслеживайте, как вы сюда попали. Итак, на шаге 1 B (A) E (A) помещается в очередь. На втором шаге B удаляется из очереди, а C (B) помещается в очередь и т. Д. Затем легко найти обратный путь, просто возвращаясь «назад».
Лучшим способом, вероятно, является создание массива, пока есть являются узлами и хранят там ссылки (что обычно и делается, например, у Дейкстры).