[Перевод] Алгоритм Дейкстры и разработка через тестирование

Здравствуйте, дорогие читатели.

Некоторые потенциальные авторы, с которыми мы общаемся, думают, что в нашем ассортименте не хватает книг по TDD. Мы думаем, как к ней подступиться. Но нам не менее интересно, что думаете о ней вы. Поэтому предлагаем под катом перевод статьи легендарного Роберта Мартина, автора шикарной книги «Чистый код». В статье (октябрь 2016 года) господин Мартин демонстрирует искусство TDD на примере алгоритма Дейкстры.

Не так давно я был на конференции SCNA, и один из коллег обратился ко мне по поводу разработки через тестирование (TDD) и алгоритма Дейкстры. Он спросил, можно ли найти серию тестов, которые привели бы нас к этому алгоритму. Мне показалось, что это будет интересное упражнение, поэтому я и решил выполнить его здесь.

Как обычно, я начал с вырожденного тестового случая

public class MinPathTest {
  @Test
public void nothing() throws Exception {
  }
}

Алгоритм Дейкстры – простой прием, позволяющий найти кратчайший путь по графу с ребрами произвольной длины. Имея начальные и конечные узлы, алгоритм выдаст вам кратчайший путь и длину этого пути.

Итак, уже с самого начала просматриваются кое-какие интересные решения. Как представить входной граф? А как — итог алгоритма? Пожалуй, большинство из этих вопросов можно будет решить потом. Пока давайте сосредоточимся на максимально вырожденном случае: пустом графе.

public void noGraph_NoPathZeroLength() throws Exception {
Assert.assertEquals("{}0", minPath(""));
}

Уже на этапе самого первого теста я стал подыскивать формат вывода. Решил представить итоговый путь как множество узлов в фигурных скобках. Длина пути выражается целым числом, следующим за скобками.

Эта нотация у меня только для тестов. Я назвал такую технику «комбинированные утверждения» (composed asserts). Мне нравится складывать утверждения в удобочитаемые инструкции.
Зачастую это означает, что для теста требуется написать простой транслятор, превращающий комбинированные утверждения в реальный API тестируемой системы.

Разумеется, чтобы пройти этот тест, достаточно написать всего лишь следующее:

private String minPath(String graph) {
return "{}0";
}

Давайте внимательнее рассмотрим этот тестовый случай. Вызов minPath – неправильный. Алгоритм Дейкстры позволяет найти кратчайший путь между двумя заданными узлами. Итак, если предположить, что узлы именованные, тест на самом деле должен выглядеть так:

Assert.assertEquals("{}0", minPath("", "A", "Z"));

Но он некрасивый. Можно сделать рефакторинг, чтобы немного его причесать:

private void assertPath(String graph, String expected) {
assertEquals(expected, minPath(graph, "A", "Z"));
}

@Test
public void noGraph_NoPathZeroLength() throws Exception {
assertPath("", "{}0");
}

Обратите внимание: метод assertPath просто предполагает, что во всех тестовых случаях мы будем использовать«A»и «Z» в качестве начальной и конечной точки.

Последнее изменение: думаю, путь и длину нужно разделить.

private void assertMinPath(String graph, 
int length, String path) {
assertEquals(length, minLength(graph, "A", "Z"));
assertEquals(path, minPath(graph, "A", "Z"));
}

@Test
public void noGraph_NoPathZeroLength() throws Exception {
assertMinPath("", 0, "{}");
}

privateintminLength(String graph, String begin, String end) {
return 0;
}

private String minPath(String graph, String begin, String end) {
return "{}";
}

Поскольку я проверяю утверждение при помощи двух методов, думаю, логично предположить, что это должны быть методы некого класса, выполняющего алгоритм Дейкстры. Итак, давайте сделаем рефакторинг с извлечением делегата, чтобы получился новый класс.

public class MinPathTest {
private void assertMinPath(String graph,
int length, String path) {
PathFinder pf = new PathFinder(graph);
assertEquals(length, pf.minLength("A", "Z"));
assertEquals(path, pf.minPath("A", "Z"));
  }

  @Test
public void noGraph_NoPathZeroLength() throws Exception {
assertMinPath("", 0, "{}");
  }
}

classPathFinder {
publicPathFinder(String graph) {
  }

publicintminLength(String begin, String end) {
return 0;
  }

public String minPath(String begin, String end) {
return "{}";
  }
}

Думаю, интересно отметить, сколько размышлений и усилий было вложено в структурирование этой проблемы; а ведь это всего лишь первый вырожденный тест. А теперь добавлю еще несколько вырожденных случаев:

@Test
public void degenerateCases() throws Exception {
assertMinPath("", 0, "{}");   //пустой граф
assertMinPath("A", 0, "{}");  //один узел
assertMinPath("B1C", 0, "{}");// нет начала и конца
assertMinPath("A1C", 0, "{}");// нет конца
assertMinPath("B1Z", 0, "{}");// нет начала
}

Эти тесты вынудили меня иначе решить ситуацию с комбинированным утверждением. В наших тестах ребро графа будет иметь структуру length. Так, B1C – ребро единичной длины, соединяющее узел B с узлом C.

Думаю, на этом с вырожденными случаями все. Итак, немного поддадим жару и обсудим первый тестовый случай, для которого потребуется хотя бы символически пошевелить мозгами.

@Test
public void oneEdge() throws Exception {
assertMinPath("A1Z", 1, "{AZ}");
}

Тест, разумеется, проваливается. Еще мне неуютно от того, что тут я проверяю две вещи сразу – путь и длину, хотя их можно было бы проверить по отдельности. Досадно потому, что я столько времени убил, составляя это комбинированное утверждение, а теперь я снова хочу его разобрать.

Но, думаю, эту ситуацию можно «хитро» обойти.

private static String ANY = null;

private void assertMinPath(String graph,
                           Integer length, String path) {
PathFinder pf = new PathFinder(graph);
if (length != null)
assertEquals((int)length, pf.minLength("A", "Z"));
if (path != null)
assertEquals(path, pf.minPath("A", "Z"));
}
...
@Test
public void oneEdge() throws Exception {
assertMinPath("A1Z", 1, ANY);
}

Так комбинированное утверждение остается нетронутым, а я при желании могу проигнорировать любой из двух компонентов. Теперь давайте добьемся прохождения теста.

Очевидно, теперь я должен сделать примерно такую непотребную вещь:

public int minLength (String begin, String end) {
if (graph.equals("A1Z"))
return 1;
return 0;
}

Но здесь я нарушаю несколько правил. Во-первых, правило универсальности, которое гласит: чем специфичнее тесты, тем более обобщен код. Иными словами, боевой код должен стать более универсальным – только так он пройдет падающий тест. В боевой код нельзя добавлять выражения, специфичные для падающего теста (гораздо подробнее об этом я рассказываю в Episode 19: Advanced TDD, на cleancoders.com).

Второе нарушенное правило – связанность тестов. Нельзя допускать сильной связи между тестами в боевом коде. Чем сильнее связывание, тем хрупче тесты. Не хочется пропагандировать решения, при которых единственное изменение в боевом коде сломает десятки или сотни тестов. В данном конкретном случае не следует допускать, чтобы комбинированное утверждение утекло в API боевого кода.

Таким образом, не следует передавать String graph в конструктор PathFinder. Это также означает, что функция minPath не должна возвращать String, используемую комбинированным утверждением.

Итак, начинаем развязывать тесты. В функции makePathFinder ниже показано, как это делается.

public class MinPathTest {
private static String ANY = null;

private void assertMinPath(String graph,
                             Integer length, String path) {
PathFinder pf = makePathFinder(graph);
if (length != null)
assertEquals((int) length, pf.minLength("A", "Z"));
if (path != null)
assertEquals(path, pf.minPath("A", "Z"));
  }

privatePathFindermakePathFinder(String graph) {
PathFinder pf = new PathFinder();
    Pattern edgePattern = 
Pattern.compile("(\\D+)(\\d+)(\\D+)");
    Matcher matcher = edgePattern.matcher(graph);
if (matcher.matches()) {
      String start = matcher.group(1);
int length = Integer.parseInt(matcher.group(2));
      String end = matcher.group(3);
pf.addEdge(start, end, length);
    }
return pf;
  }

  @Test
public void degenerateCases() throws Exception {
assertMinPath("", 0, "{}");   // пустой граф
assertMinPath("A", 0, "{}");  // один узел
assertMinPath("B1C", 0, "{}");// нет начала и конца
assertMinPath("A1C", 0, "{}");// нет конца
assertMinPath("B1Z", 0, "{}");// нет начала
  }

  @Test
public void oneEdge() throws Exception {
assertMinPath("A1Z", 1, ANY);
  }
}

classPathFinder {
private List<Edge> edges = new ArrayList<>();

publicPathFinder() {
  }

publicintminLength(String begin, String end) {
int length = 0;
for (Edge edge : edges) {
if (edge.begin.equals(begin) &&edge.end.equals(end))
length += edge.length;
    }
return length;
  }

public String minPath(String begin, String end) {
return "{}";
  }

public void addEdge(String start, String end, int length) {
edges.add(new Edge(start, end, length));
  }

private static class Edge {
public final String begin;
public final String end;
public final int length;

public Edge(String begin, String end, int length) {
this.begin = begin;
this.end = end;
this.length = length;
    }
  }
}

Обратите внимание: синтаксический разбор скомбинированного утверждения остается в тестовом классе. Классу PathFinder ничего не известно о потешном синтаксисе моих тестов. Также, подчеркиваю: чтобы тесты выполнялись, в боевом коде должно предполагаться, что у графа всего одно ребро. Имею в виду, что мы должны избавиться от этого ANY.

assertMinPath("A1Z", 1, "{AZ}");

Итак, соберем список узлов, имеющихся в пути. Список? Ах, да, есть же синтаксис
toString для списков. Этот тест, а также все последующие придется изменить следующим образом:

@Test
public void degenerateCases() throws Exception {
assertMinPath("", 0, "[]");   // пустой граф
assertMinPath("A", 0, "[]");  // один узел
assertMinPath("B1C", 0, "[]"); // нет начала или конца
assertMinPath("A1C", 0, "[]"); // нет конца
assertMinPath("B1Z", 0, "[]"); // нет начала
}

@Test
public void oneEdge() throws Exception {
assertMinPath("A1Z", 1, "[A, Z]");
}

Теперь, чтобы пройти этот тест, нужно изменить вспомогательную тестовую функцию assertMinPath, добавив вызов toString.
…

if (path != null)
assertEquals(path, pf.minPath("A", "Z").toString());
...

Добавляем список path к PathFinder и просто загрузим его в функции minLength.

classPathFinder {
private List<Edge> edges = new ArrayList<>();
  ...

publicintminLength(String begin, String end) {
int length = 0;
for (Edge edge : edges) {
if (edge.begin.equals(begin) &&edge.end.equals(end)) {
length += edge.length;
path.add(edge.begin);
path.add(edge.end);
      }
    }
return length;
  }

public List<String>minPath(String begin, String end) {
return path;
  }
...

Работает. Но мне не нравится, что minLength вдобавок еще вычисляет путь. Думаю, вычисления и отчетность нужно разделить.

private void assertMinPath(String graph,
                             Integer length, String path) {
PathFinder pf = makePathFinder(graph);
if (length != null)
assertEquals((int) length, pf.getLength());
if (path != null)
assertEquals(path, pf.getPath().toString());
  }

privatePathFindermakePathFinder(String graph) {
PathFinder pf = new PathFinder();
    ...
pf.findPath("A", "Z");
return pf;
  }

classPathFinder {
private List<Edge> edges = new ArrayList<>();
private List<String> path = new ArrayList<>();
privateint length;

  ...

publicintgetLength() {
return length;
  }

public List<String>getPath() {
return path;
  }

...

Уже лучше. А теперь убедимся, что у нас получается правильная длина.

assertMinPath("A2Z", 2, "[A, Z]");

Ага, все отлично работает. Попробуем с двумя последовательными ребрами

Test
public void twoEdges() throws Exception {
assertMinPath(«A1B,B1Z», 2, ANY);
}

Как и следовало ожидать, тест не пройден, получаем нулевую длину. Чтобы пройти его, понадобится разбирать множество ребер во вспомогательной функции makePathFinder. Это довольно просто. Просто рассекаем граф по запятой и ставим в цикле матчер регулярных выражений.

privatePathFinder makePathFinder(String graph) {
PathFinder pf = new PathFinder();
  Pattern edgePattern = Pattern.compile("(\\D+)(\\d+)(\\D+)");
String[] edges = graph.split(",");
for (String edge : edges) {
    Matcher matcher = edgePattern.matcher(edge);
if (matcher.matches()) {
      String start = matcher.group(1);
int length = Integer.parseInt(matcher.group(2));
      String end = matcher.group(3);
pf.addEdge(start, end, length);
    }
  }
pf.findPath("A", "Z");
return pf;
}

Разумеется, тест по-прежнему падает, так что теперь нам потребуется соединить два ребра. Предположим, что ребра указываются в определенном порядке, так что первое ребро начинается с узла A, а второе заканчивается узлом Z. В таком случае мы обеспечим все соединение, заменив && на || в функции findPath:

public void findPath(String begin, String end) {
length = 0;
for (Edge edge : edges) {
if (edge.begin.equals(begin) || edge.end.equals(end)) {
length += edge.length;
path.add(edge.begin);
path.add(edge.end);
    }
  }
}

Нравится такая замена? && на ||. Да, неглупо. Работать такое решение будет только с двумя последовательными ребрами. Мы уже строим наполеоновские планы. Но, все-таки, оно не годится.

О, мы справляемся с тестом twoEdges, и с тестами oneEdge, но проваливаем тесты degenerateCases.

Чтобы пройти все эти тесты, мне нужна реализация, которая дает нулевую длину и пустой путь, если пути от A до Z не существует. Теперь, поскольку я не знаю, сколько здесь ребер (их может быть ноль, одно или два), я не могу просто взять два. Вместо этого я по отдельности анализирую все три случая: если ребра отсутствуют, ребро одно либо ребер два. Получается следующий код:

public void findPath(String begin, String end) {
if (edges.size() == 0)
return;

else if (edges.size() == 1) {
    Edge edge = edges.get(0);
if (edge.begin.equals(begin) &&edge.end.equals(end)) {
path.add(edge.begin);
path.add(edge.end);
length += edge.length;
    }
  } else {
for (Edge edge : edges) {
if (edge.begin.equals(begin) || edge.end.equals(end)) {
path.add(edge.begin);
path.add(edge.end);
length += edge.length;
      }
    }
  }
}

Ага, оно работает, но выглядит ужасно. Решение не только нарушает правило универсальности; оно попросту омерзительно. Более того, код неправильно собирает путь. Например, assertMinPath ("A1B, B1Z", 2, "[A, B, Z]"); проваливается, поскольку дает [A, B, B, Z]. Это можно было бы пофиксить, добавив еще один ужасный оператор if ; но есть идея получше. Давайте снова пройдем граф с начала и до конца.

public void findPath(String begin, String end) {
  List<String> p = new ArrayList<>();
int l = 0;
p.add(begin);

for (Edge e = findEdge(begin); 
e != null; e = findEdge(e.end)) {
p.add(e.end);
    l += e.length;
if (e.end.equals(end)) {
length = l;
path = p;
return;
    }
  }
}

private Edge findEdge(String begin) {
for (Edge e : edges) {
if (e.begin.equals(begin))
return e;
  }
return null;
}  

Окей, это работает. Странно, что приходится использовать временные переменные длины и пути; но я не вижу другого способа проигнорировать несуществующие пути. Также полагаю, что это решение позволяет устранить зависимость от порядка узлов.

@Test
public void twoEdges() throws Exception {
assertMinPath ("A1B,B1Z", 2, "[A, B, Z]");
assertMinPath ("B1Z,A1B", 2, "[A, B, Z]");
assertMinPath ("A1X,Y1Z", 0, "[]");
}

Да. Все проходит. Думаю, будет работать и с тремя, и с большим количеством ребер. То же касается графов, в которых есть всего один полный путь, а остальные пути висящие.

@Test
public void threeEdges() throws Exception {
assertMinPath ("A2B,B3C,C4Z", 9, "[A, B, C, Z]");
assertMinPath ("B3C,C4Z,A2B", 9, "[A, B, C, Z]");
}

@Test
public void OnlyOnePath() throws Exception {
assertMinPath ("A1B,B2C,C3Z,B4D,D6E", 6, "[A, B, C, Z]");
}

Но вот этот проваливается, поскольку при обходе графа не находим ребра C3Z.

assertMinPath ("A1B,B2C,C3D,C3Z", 6, "[A, B, C, Z]");

Окей. Итак, мы не можем просто обойти граф по порядку. Вместо этого нам придется проверить все возможные пути, идущие от стартового узла; по ходу дела придется записывать временные переменные, и так пока не доберемся до конца.

Далее можно убедиться, что для этого потребуется изрядно повозиться: отслеживать все узлы, а также пути, ассоциированные с этими узлами, и длины путей. Но в остальном алгоритм практически не изменился.

Отличается итерация цикла. Цикл стартует с начального узла, а затем обходит все непосещенные соседние узлы, сохраняет на этих соседних узлах суммарные длины и пути.

Обратите внимание: я использую Integer.MAX_VALUE в качестве сигнального значения: «недостижимо от посещенного узла». Поиск ограничивается лишь теми узлами, которые удалось достичь, поскольку мы все еще идем от начала к концу. Любой узел, которого не удалось достичь, очевидно, не является следующим на пути.

classPathFinder {
private List<Edge> edges = new ArrayList<>();
private Set<String>nodeNames = new HashSet<>();
private Map<String, Node> nodes = new HashMap<>();
private Node endNode;

public void findPath(String begin, String end) {
    List<String> unvisited = initializeSearch(begin, end);

for (String node = begin; 
node != null; node = getNext(unvisited)) {
unvisited.remove(node);
visit(node);
    }

setupEndNode(end);
  }

private List<String>initializeSearch(String begin, 
                                        String end) {
nodeNames.add(begin);
nodeNames.add(end);
    List<String> unvisited = new ArrayList<>(nodeNames);
for (String node : unvisited)
nodes.put(node, new Node(Integer.MAX_VALUE));

nodes.get(begin).length = 0;
return unvisited;
  }

private void visit(String node) {
    List<Edge> neighbors = findEdges(node);
    Node curNode = nodes.get(node);
for (Edge e : neighbors) {
      Node nbr = nodes.get(e.end);
nbr.length = curNode.length + e.length;
nbr.path = new ArrayList<String>();
nbr.path.addAll(curNode.path);
nbr.path.add(node);
    }
  }

private void setupEndNode(String end) {
endNode = nodes.get(end);
if (endNode.length != Integer.MAX_VALUE)
endNode.path.add(end);
else
endNode.length = 0;
  }

private String getNext(List<String> unvisited) {
for (String name : unvisited) {
      Node candidate = nodes.get(name);
if (candidate.length != Integer.MAX_VALUE)
return name;
    }
return null;
  }

private List<Edge>findEdges(String begin) {
    List<Edge> found = new ArrayList<>();
for (Edge e : edges) {
if (e.begin.equals(begin))
found.add(e);
    }
return found;
  }

publicintgetLength() {
returnendNode.length;
  }

public List<String>getPath() {
returnendNode.path;
  }

public void addEdge(String start, String end, int length) {
edges.add(new Edge(start, end, length));
nodeNames.add(start);
nodeNames.add(end);
  }

private static class Edge {
public final String begin;
public final String end;
public final int length;

public Edge(String begin, String end, int length) {
this.begin = begin;
this.end = end;
this.length = length;
    }
  }

private static class Node {
publicint length;
public List<String> path;

public Node(int l) {
this.length = l;
this.path = new ArrayList<>();
    }
  }
}

Проходит. Теперь нужно добавить тест, в котором есть параллельные пути. Вот простой явно провальный тест:

assertMinPath ("A1B,B2Z,A1Z", 1, "[A, Z]");

Действительно, падает.

Чтобы пройти этот тест, необходимо определить, когда два пути сойдутся. Это просто. Если длина до целевого узла не равна Integer.MAX_VALUE, то этот узел достигнут по другому пути. Поскольку нас интересует минимум, можно просто установить значение длины на этом узле в качестве минимума для сходящихся путей. Оказывается, значение Integer.MAX_VALUE очень удобно в качестве сигнальной метки, поскольку заменяет «бесконечную» длину.

private void visit(String node) {
  List<Edge> neighbors = findEdges(node);
  Node curNode = nodes.get(node);
for (Edge e : neighbors) {
    Node nbr = nodes.get(e.end);

intnewLength = curNode.length + e.length;
if (nbr.length>newLength) {
nbr.length = newLength;
nbr.path = new ArrayList<String>();
nbr.path.addAll(curNode.path);
nbr.path.add(node);
    }
  }
}

Пожалуй, можно немного ускорить алгоритм, если прекращать поиск сразу после того, как будет посещен конечный узел.

for (String node = begin; node != null && !node.equals(end); node = getNext(unvisited)) {
unvisited.remove(node);
visit(node);
}

А чтобы еще сильнее его ускорить, можно отдавать приоритет поиску непосещенных узлов, достижимых по кратчайшим путям.

private String getNext(List<String> unvisited) {
  String minNodeName = null;
intminLength = Integer.MAX_VALUE;

for (String name : unvisited) {
    Node candidate = nodes.get(name);
if (candidate.length<minLength) {
minLength = candidate.length;
minNodeName = name;
    }
  }
return minNodeName;
}

По всем параметрам этот алгоритм является алгоритмом Дейкстры. Реализация не очень быстрая, поскольку я пользовался списками и множествами, а также кучей неэффективных структур. Чтобы еще сильнее его разогнать, потребуется хорошо потрудиться. Более того, в алгоритм вплетены некоторые допущения, от которых следовало бы избавиться. В частности, предполагается, что входной граф является направленным, тогда как в универсальном алгоритме такое допущение не делается. В конце концов, весь код нуждается в некотором рефакторинге.

Но я стремился проверить, позволяет ли TDD выполнить пошаговую проверку алгоритма Дейкстры. Думаю, да, но, должен сказать, что такой подход получился довольно несуразным. Выполняя эти первые несколько тестов, мне пришлось прибегнуть к нескольким гипотетическим алгоритмам, между которыми нет гладких переходов. Однако, каждый последующий тест выявлял изъяны предыдущего решения, которые удавалось исправить без особого труда.

Найдется ли более качественная последовательность тестов, которая позволит прийти к алгоритму Дейкстры не столь окольным путем? Возможно, но, если так – то я ее не нашел.

В любом случае, было интересно. Спасибо слушателю, который подсказал мне эту задачу.
Вот готовый код, который еще нужно немножечко причесать (уважаемый читатель, эту задачу оставляю вам в качестве домашней работы ;))

packagedijkstrasAlg;

importorg.junit.Test;

importjava.util.*;
importjava.util.regex.Matcher;
importjava.util.regex.Pattern;

import static org.junit.Assert.assertEquals;

public class MinPathTest {
private static String ANY = null;

private void assertMinPath(String graph,
                             Integer length, String path) {
PathFinder pf = makePathFinder(graph);
if (length != null)
assertEquals((int) length, pf.getLength());
if (path != null)
assertEquals(path, pf.getPath().toString());
  }

privatePathFindermakePathFinder(String graph) {
PathFinder pf = new PathFinder();
    Pattern edgePattern = 
Pattern.compile("(\\D+)(\\d+)(\\D+)");
String[] edges = graph.split(",");
for (String edge : edges) {
      Matcher matcher = edgePattern.matcher(edge);
if (matcher.matches()) {
        String start = matcher.group(1);
int length = Integer.parseInt(matcher.group(2));
        String end = matcher.group(3);
pf.addEdge(start, end, length);
      }
    }
pf.findPath("A", "Z");
return pf;
  }

  @Test
public void degenerateCases() throws Exception {
assertMinPath("", 0, "[]");   // пустой граф
assertMinPath("A", 0, "[]");  // один узел
assertMinPath("B1C", 0, "[]");// нет начала или конца
assertMinPath("A1C", 0, "[]");// нет конца
assertMinPath("B1Z", 0, "[]");// нет начала
  }

  @Test
public void oneEdge() throws Exception {
assertMinPath("A1Z", 1, "[A, Z]");
assertMinPath("A2Z", 2, "[A, Z]");
  }

  @Test
public void twoEdges() throws Exception {
assertMinPath("A1B,B1Z", 2, "[A, B, Z]");
assertMinPath("B1Z,A1B", 2, "[A, B, Z]");
assertMinPath("A1X,Y1Z", 0, "[]");
  }

  @Test
public void threeEdges() throws Exception {
assertMinPath("A2B,B3C,C4Z", 9, "[A, B, C, Z]");
assertMinPath("B3C,C4Z,A2B", 9, "[A, B, C, Z]");
  }

  @Test
public void OnlyOnePath() throws Exception {
assertMinPath("A1B,B2C,C3Z,B4D,D6E", 6, "[A, B, C, Z]");
assertMinPath("A1B,B2C,C3D,C3Z", 6, "[A, B, C, Z]");
  }

  @Test
public void parallelPaths() throws Exception {
assertMinPath("A1B,B2Z,A1Z", 1, "[A, Z]");
assertMinPath("A1B,A1C,A2D,C5E,B8E,C1F,D3F,F2G,G3Z,E2G",
                   7,"[A, C, F, G, Z]");
  }
}

classPathFinder {
private List<Edge> edges = new ArrayList<>();
private Set<String>nodeNames = new HashSet<>();
private Map<String, Node> nodes = new HashMap<>();
private Node endNode;

public void findPath(String begin, String end) {
    List<String> unvisited = initializeSearch(begin, end);

for (String node = begin; 
node != null && !node.equals(end); 
node = getNext(unvisited)) {
unvisited.remove(node);
visit(node);
    }

setupEndNode(end);
  }

private List<String>initializeSearch(String begin, 
                                        String end) {
nodeNames.add(begin);
nodeNames.add(end);
    List<String> unvisited = new ArrayList<>(nodeNames);
for (String node : unvisited)
nodes.put(node, new Node(Integer.MAX_VALUE));

nodes.get(begin).length = 0;
return unvisited;
  }

private void visit(String node) {
    List<Edge> neighbors = findEdges(node);
    Node curNode = nodes.get(node);
for (Edge e : neighbors) {
      Node nbr = nodes.get(e.end);

intnewLength = curNode.length + e.length;
if (nbr.length>newLength) {
nbr.length = newLength;
nbr.path = new ArrayList<String>();
nbr.path.addAll(curNode.path);
nbr.path.add(node);
      }
    }
  }

private void setupEndNode(String end) {
endNode = nodes.get(end);
if (endNode.length != Integer.MAX_VALUE)
endNode.path.add(end);
else
endNode.length = 0;
  }

private String getNext(List<String> unvisited) {
    String minNodeName = null;
intminLength = Integer.MAX_VALUE;

for (String name : unvisited) {
      Node candidate = nodes.get(name);
if (candidate.length<minLength) {
minLength = candidate.length;
minNodeName = name;
      }
    }
returnminNodeName;
  }

private List<Edge>findEdges(String begin) {
    List<Edge> found = new ArrayList<>();
for (Edge e : edges) {
if (e.begin.equals(begin))
found.add(e);
    }
return found;
  }

publicintgetLength() {
returnendNode.length;
  }

public List<String>getPath() {
returnendNode.path;
  }

public void addEdge(String start, String end, int length) {
edges.add(new Edge(start, end, length));
nodeNames.add(start);
nodeNames.add(end);
  }

private static class Edge {
public final String begin;
public final String end;
public final int length;

public Edge(String begin, String end, int length) {
this.begin = begin;
this.end = end;
this.length = length;
    }
  }

private static class Node {
publicint length;
public List<String> path;

public Node(int l) {
this.length = l;
this.path = newArrayList<>();
    }
  }
}

Let's block ads! (Why?)