Algorytm Dijkstry

Byłem jednego dnia na SCNA, i ktoś zagadnął mnie o TDD i algorytm Dijkstry. Zastanawiał się, czy można znaleźć sekwencję testów, która zaprowadzi do tego algorytmu. To wyglądało mi na fajne, krótkie ćwiczenie, więc zdecydowałem się spróbować.

---

Poniższy tekst jest luźnym tłumaczeniem wpisu bloga Roberta Cecila "Wujka Boba" Martina ze strony:

https://blog.cleancoder.com/uncle-bob/2016/10/26/DijkstrasAlg.html

Proszę o komentarze, jeżeli ta luźność jest zbyt daleko posunięta.

---

Zacząłem tak, jak zwykle; przez odpalenie ograniczonego przypadku testowego.

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

Algorytm Dijkstry jest prostym sposobem znajdowania najkrótszej drogi w grafie o krawędziach mających konkretną długość. Podając węzeł startowy i końcowy, algorytm wskaże, jaka jest najkrótsza ścieżka i jaka jest jej długość.

A więc już od samego początku są ciekawe decyzje do podjęcia. W jaki sposób powinienem przedstawiać wejściowy graf? Jak powinienem przedstawiać wyjście tego algorytmu? O większości tego możemy prawdopodobnie zadecydować później. Na teraz, powinniśmy skoncentrować się na najbardziej ograniczonym przypadku: pustym grafie.

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

Ten pierwszy test zmusił mnie, abym podjął jakieś decyzje o formacie wyjścia. Będę prezentował wyjściową ścieżkę jako zbiór węzłów pomiędzy nawiasami klamrowymi. Długość ścieżki będzie liczbą całkowitą za nawiasami klamrowymi.

Ta notacja jest tylko na potrzeby moich testów. Używam techniki, którą nazywam skomponowanymi asercjami. Lubię komponować moje asercje w zdania, które czyta się łatwo. To zwykle oznacza, że muszę pisać proste translatory, które zamieniają skomponowane asercje na rzeczywiste API systemu poddawanego testom.

To jasne, że mogę sprawić, aby ten test przechodził, nie używając niczego więcej niż tego:

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

Popatrzmy wnikliwie na ten przypadek testowy. Nie jest właściwe takie wywołanie metody minPath. Algorytm Dijkstry znajduje najkrótszą ścieżkę pomiędzy dwoma określonymi węzłami. Więc zakładając, że węzły mają nazwy, test powinien naprawdę wyglądać jakoś tak:

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

To brzydko wygląda. Możemy zrefaktorować to tak, aby było odrobinę ładniejsze:

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

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

Zauważ, że metoda assertPath dla prostoty zakłada, że wszystkie przypadki testowe będą używać "A" i "Z" jako ich pozycji startowych i końcowych.

Jedna, ostatnia zmiana. Myślę, że ścieżka i jej długość powinny być oddzielone.

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, "{}");
}

private int minLength(String graph, String begin, String end) {
  return 0;
}

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

Ponieważ są dwie metody do sprawdzenia w mojej asercji, myślę, że sensownym byłoby założyć, że powinny one być metodami tej samej klasy uruchamiającej algorytm Dijkstry. Użyjmy więc refaktoringu typu wyciągnij delegata, aby wyciągnąć to do nowej klasy.

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, "{}");
  }
}

class PathFinder {
  public PathFinder(String graph) {
  }

  public int minLength(String begin, String end) {
    return 0;
  }

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

Uważam to za interesujące, że już tak dużo namysłu i wysiłku zostało włożone w strukturę tego problemu — dla jednego tylko, ograniczonego przypadku testowego. Ale teraz myślę, że możemy dodać kilka innych ograniczonych przypadków:

@Test
public void degenerateCases() throws Exception {
  assertMinPath("", 0, "{}");   //pusty graf
  assertMinPath("A", 0, "{}");  //jeden węzeł
  assertMinPath("B1C", 0, "{}");//nie ma ani początku ani końca
  assertMinPath("A1C", 0, "{}");//nie ma końca
  assertMinPath("B1Z", 0, "{}");//nie ma początku
}

Te testy zmusiły mnie, aby podjąć kolejną decyzję o skomponowanej asercji. Dla naszych testów struktura krawędzi grafu będzie wyglądała tak: <nazwa>długość<nazwa>. Więc B1C jest krawędzią o długości 1, która łączy węzeł B i C.

Myślę, że wszystkie te przypadki testowe są dość ograniczone. Więc przekręćmy koło zębate skomplikowania o jeden ząbek w górę i stwórzmy test, który zmusi nas do zrobienia czegoś choć trochę bardziej sprytnego.

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

Ten test, oczywiście, nie przejdzie. Czuję też pewien dyskomfort, ponieważ testuję dwie rzeczy naraz, długość i ścieżkę, które mogłyby być testowane oddzielnie. Wyjdę teraz na zrzędę, bo poświęciłem tyle czasu na wprowadzenie skomponowanej asercji; i teraz chciałbym ją rozbić znowu. Ale myślę, że jest jeden "sprytny" sposób na obejście tego:

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);
}

To pozostawia moją skomponowaną asercję nietkniętą, i pozwala mi pominąć dowolną z tych dwóch komponentów na życzenie. A teraz sprawmy, żeby ten test przechodził.

Teraz, oczywiście, mógłbym zrobić coś tak ohydnego, jak to:

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

Ale to łamie kilka zasad. Po pierwsze, to łamie zasadę ogólności, która mówi: W miarę, jak testy robią się bardziej konkretne, kod robi się bardziej ogólny. Innymi słowy, kod produkcyjny musi stać się bardziej ogólny, aby spełnić test, który nie przechodzi. Do produkcyjnego kodu nie możesz dodawać wyrażeń, które są specyficzne dla danego testu. (Mówię o tym dużo więcej w Odcinku 19: Zaawansowane TDD, na cleancoders.com)

Drugą złamaną zasadą jest zależność testów. Nie chcemy, aby testy stały się mocno zależne od produkcyjnego kodu. Im więcej zależności, tym bardziej testy stają się kruche. Nie chcemy doprowadzić do sytuacji, gdy pojedyncza zmiana w kodzie produkcyjnym zepsuje dziesiątki czy setki testów.

To oznacza, że nie powinienem przekazywać String graph do konstruktora klasy PathFinder. To też oznacza, że funkcja minPath nie powinna zwracać String używanego przez skomponowaną asercję.

A więc teraz jest czas, aby zacząć uniezależniać testy. Funkcja makePathFinder poniżej pokazuje, jak to zrobiłem.

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"));
  }

  private PathFinder makePathFinder(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, "{}");   //empty graph
    assertMinPath("A", 0, "{}");  //one node
    assertMinPath("B1C", 0, "{}");//no start or end
    assertMinPath("A1C", 0, "{}");//no end
    assertMinPath("B1Z", 0, "{}");//no start
  }

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

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

  public PathFinder() {
  }

  public int minLength(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;
    }
  }
}

Zauważ, że całe parsowanie dla skomponowanej asercji pozostaje w klasie testowej. Klasa PathFinder nie wie nic o tej śmiesznej składni, której używam w testach. Zauważ także, że aby testy przechodziły, kod produkcyjny musi zakładać, że wykres ma tylko jedną krawędź. To założenie zamierzamy złamać w kolejnych kilku testach. W międzyczasie powinniśmy pozbyć się tego ANY.

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

Więc zamierzam zbudować listę węzłów w ścieżce. Listę? Aaaa, jest składnia toString dla list. Powinniśmy zmienić ten test i wszystkie inne testy następująco:

@Test
public void degenerateCases() throws Exception {
  assertMinPath("", 0, "[]");   //pusty graf
  assertMinPath("A", 0, "[]");  //jeden węzeł
  assertMinPath("B1C", 0, "[]");//nie ma ani początku ani końca
  assertMinPath("A1C", 0, "[]");//nie ma końca
  assertMinPath("B1Z", 0, "[]");//nie ma początku
}

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

Teraz, aby to przechodziło, dodamy w funkcji pomocniczej assertMinPath wywołanie toString.

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

Dodamy listę węzłów path do PathFindera i po prostu zwrócimy ją w minLength.

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

  public int minLength(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;
  }
...

To działa. Ale nie podoba mi się fakt, że minLength również oblicza ścieżkę. Myślę, że powinniśmy oddzielić obliczenia od raportowania.

  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());
  }

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

class PathFinder {
  private List<Edge> edges = new ArrayList<>();
  private List<String> path = new ArrayList<>();
  private int length;

  ...

  public int getLength() {
    return length;
  }

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

...

OK, teraz lepiej. Teraz, upewnijmy się, że dostajemy prawidłową długość.

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

Taaa, to działa całkiem nieźle. Więc spróbujmy dwóch następujących po sobie krawędzi.

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

To nie przechodzi, jak należało się spodziewać, dając nam w wyniku długość zero. Aby to przechodziło, musimy umieć parsować wiele krawędzi w funkcji pomocniczej makePathFinder. To jest całkiem proste. Tylko podziel graf na przecinkach, i wrzuć dopasowanie wyrażeń regularnych w pętlę.

private PathFinder 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;
}

Oczywiście to nadal nie sprawia, że test przechodzi, więc teraz zamierzamy połączyć dwie krawędzie. Załóżmy, że krawędzie są ułożone po kolei, więc wierzchołek A rozpoczyna pierwszą krawędź, i wierzchołek Z kończy drugą krawędź. Przy takim założeniu, możemy ustawić całe połączenie poprzez zmianę warunku && na || w funkcji 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);
    }
  }
}

Podoba Ci się ta zmiana? && na ||. Taaak, całkiem sprytnie. To zadziała tylko dla dwóch kolejnych krawędzi. Założenia wznoszą się w niebiosa! I, tak czy inaczej, to nie działa.

Ooo, przechodzą testy twoEdges, i testy oneEdge, ale nie przechodzą testy degenerateCases. I to nie dziwota, ponieważ tylko nasze dwa ostatnie ograniczone przypadki testowe pasują do założenia "A" pierwszy lub "Z" ostatni.

Aby wszystkie te testy przechodziły, potrzebuję implementacji, która w wyniku daje zerową długość i pustą ścieżkę, jeżeli nie istnieje ścieżka pomiędzy A i Z. Ponieważ nie wiem, ile będzie krawędzi (może być zero, jeden, dwie) nie mogę wziąć tylko dwóch. Zamiast tego, mógłbym zrobić analizę przypadków dla zera, jednej lub dwóch krawędzi; jak poniżej:

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;
      }
    }
  }
}

OK, to działa, ale to jest naprawdę okropne. Nie tylko łamie zasadę ogólności; to jest po prostu ohydne. Co więcej, nie do końca poprawnie tworzy ścieżkę. Na przykład test: assertMinPath("A1B,B1Z", 2, "[A, B, Z]"); nie przechodzi, ponieważ tworzy [A, B, B, Z]. Mógłbym to naprawić przez dodanie jeszcze jednej okropnej instrukcji if; ale mam lepszy pomysł. Przejdźmy graf od początku do końca.

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;
}

OK, działa. To osobliwe, że musieliśmy użyć tymczasowych zmiennych length i path; ale to jedyny sposób, jaki przychodzi mi na myśl, na ignorowanie ścieżek, które nie istnieją. Myślę także, że to rozwiązanie pozbawia nas zależności od kolejności.

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

Tak, wszystkie przechodzą. Myślę, że trzy i więcej krawędzi też zadziała. I także grafy z jedną kompletną ścieżką i pozostałymi dyndającymi ścieżkami.

@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]");
}

Ale to nie będzie przechodzić, ponieważ przejście przez graf pomija krawędź C3Z.

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

Ok. Więc nie możemy po prostu przejść grafu po kolei. W zamian to, co musimy zrobić, to sprawdzić każdą możliwą drogę, która wychodzi z wierzchołka startowego; i przez całą tę drogę musimy zapisywać nasze tymczasowe znaleziska, aż dojdziemy do końca.

Jak zobaczysz poniżej, to wymaga odrobinę mrówczego wysiłku. Muszę śledzić wszystkie wierzchołki, i ścieżki i długości połączone z tymi wierzchołkami. Ale, poza tym, algorytm jest prawie taki sam jak do tej pory.

Iteracja w pętli jest inna. Zaczyna się w początkowym wierzchołku, i potem przechodzi przez wszystkich nieodwiedzonych sąsiadów, i zapisuje dodane długości i ścieżki w tych sąsiadach.

Zauważ, że użyłem Integer.MAX_VALUE jako strażnika, który oznacza "Nieodwiedzony z odwiedzonego wierzchołka". Ograniczamy limit wyszukiwania do tylko tych wierzchołków, które były odwiedzone, ponieważ przecież idziemy od początku do końca. Każdy węzeł, który nie był odwiedzony, oczywiście, nie może być następnym w ścieżce.

class PathFinder {
  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;
  }

  public int getLength() {
    return endNode.length;
  }

  public List<String> getPath() {
    return endNode.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 {
    public int length;
    public List<String> path;

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

To przechodzi. Więc teraz potrzebujemy dodać test grafu, który ma równoległe ścieżki. Tu mam jeden prosty, który powinien nie przechodzić:

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

I nie przechodzi

Aby sprawić, żeby to przechodziło, musimy wykryć, czy dwie ścieżki zbiegają się w jednym węźle. To proste. Jeżeli długość na węźle docelowym nie wynosi Integer.MAX_VALUE to oznacza, że inna ścieżka już osiągnęła ten węzeł. Ponieważ szukamy minimum, możemy po prostu ustawić długość na tym węźle na minimalną wartość spośród zbiegających się w tym węźle ścieżek. Wartość Integer.MAX_VALUE wydaje się byc bardzo przydatna dla tego sprawdzenia, ponieważ jest zamiennikiem dla "nieskończonej" długości.

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);

    int newLength = 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);
    }
  }
}

Prawdopodobnie możemy przyspieszyć troszkę algorytm, kończąc poszukiwania, kiedy osiągniemy węzeł końcowy.

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

I zapewne możemy przyspieszyć algorytm nawet bardziej przez preferowanie przeszukiwania nieodwiedzonych węzłów, które zostały odwiedzone przez najkrótszą ścieżkę.

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

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

To, w każdym możliwym sensie, jest algorytm Dijkstry. Ta implementacja nie jest szybka, ponieważ użyłem zbiorów i list, i mnóstwa nieefektywnych struktur. Przyspieszenie tego zajęłoby całkiem sporo roboty. Co więcej, są tam wbudowane pewne założenia, które należałoby naprawić. Przede wszystkim, jest założenie, że graf wejściowy musi być skierowany; natomiast ogólny algorytm nie wymaga takiego założenia. Na koniec, całości przydałaby się odrobina refaktoringu.

Ale celem było zobaczenie, czy możliwe jest wykorzystanie TDD do dojścia do algorytmu Dijkstry krok po kroku. Moim zdaniem jest możliwe; chociaż, muszę przyznać, że to podejście było trochę szarpane. Te kilka początkowych testów prowadziły mnie przez rząd niepewnych algorytmów, które nie bardzo chciały ewoluować jeden w drugi. Nie mniej, każdy nowy test ujawniał słabości we wcześniejszych implementacjach, które mogły być naprawione w stosunkowo prosty sposób.

Czy jest lepsza sekwencja testów, która prowadzi bardziej wprost do algorytmu Dijkstry, bez tej niepewnej szarpaniny? Być może; ale jeśli tak, nie znalazłem ich.

Mimo wszystko, było to zabawne ćwiczenie. Dziękuję uczestnikowi SCNA za zaproponowanie tego.

Końcowy kod, który nadal potrzebuje troszeczkę posprzątania (pozostawiam czytelnikowi jako ćwiczenie ;-)

package dijkstrasAlg;

import org.junit.Test;

import java.util.*;
import java.util.regex.Matcher;
import java.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());
  }

  private PathFinder 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;
  }

  @Test
  public void degenerateCases() throws Exception {
    assertMinPath("", 0, "[]");   //empty graph
    assertMinPath("A", 0, "[]");  //one node
    assertMinPath("B1C", 0, "[]");//no start or end
    assertMinPath("A1C", 0, "[]");//no end
    assertMinPath("B1Z", 0, "[]");//no start
  }

  @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]");
  }
}

class PathFinder {
  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);

      int newLength = 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;
    int minLength = Integer.MAX_VALUE;

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

  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;
  }

  public int getLength() {
    return endNode.length;
  }

  public List<String> getPath() {
    return endNode.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 {
    public int length;
    public List<String> path;

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

---

Powyższy tekst jest luźnym tłumaczeniem wpisu bloga Roberta Cecila "Wujka Boba" Martina ze strony:

https://blog.cleancoder.com/uncle-bob/2016/10/26/DijkstrasAlg.html

Proszę o komentarze, jeżeli ta luźność jest zbyt daleko posunięta.

---

[Kod źródłowy jest dostępny tutaj. - przyp. tłum.]