Algorytm Dijkstry

michalkulinski.blogspot.com 5 lat temu

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, o ile 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ą interesujące 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, iż muszę pisać proste translatory, które zamieniają skomponowane asercje na rzeczywiste API systemu poddawanego testom.

To jasne, iż 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 adekwatne 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, iż 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ż, iż metoda assertPath dla prostoty zakłada, iż wszystkie przypadki testowe będą używać "A" i "Z" jako ich pozycji startowych i końcowych.

Jedna, ostatnia zmiana. Myślę, iż ś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ę, iż sensownym byłoby założyć, iż 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, iż 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ę, iż 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: długość. Więc B1C jest krawędzią o długości 1, która łączy węzeł B i C.

Myślę, iż 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 w wprowadzenie skomponowanej asercji; i teraz chciałbym ją rozbić znowu. Ale myślę, iż 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, iż nie powinienem przekazywać String graph do konstruktora klasy PathFinder. To też oznacza, iż 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 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ż, iż 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, iż aby testy przechodziły, kod produkcyjny musi zakładać, iż 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 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 minPath(String begin, String end) {
    return path;
  }
...

To działa. Ale nie podoba mi się fakt, iż minLength również oblicza ścieżkę. Myślę, iż 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 edges = new ArrayList<>();
  private List path = new ArrayList<>();
  private
int length;

  ...

  public
int getLength() {
    return length;
  }

  public List getPath() {
    return path;
  }

...

OK, teraz lepiej. Teraz, upewnijmy się, iż 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 przez cały czas nie sprawia, iż test przechodzi, więc teraz zamierzamy połączyć dwie krawędzie. Załóżmy, iż 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ę, o ile 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 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, iż 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, iż 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ę, iż 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ż, iż 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 edges = new ArrayList<>();
  private Set nodeNames = new HashSet<>();
  private Map nodes = new HashMap<>();
  private Node endNode;

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

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

    setupEndNode(end);
  }

  private List initializeSearch(String begin,
                                     String end) {
    nodeNames.add(begin);
    nodeNames.add(end);
    List 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 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();
      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 unvisited) {
    for (String name : unvisited) {
      Node candidate = nodes.get(name);
      if (candidate.length != Integer.MAX_VALUE)
        return name;
    }
    return
null;
  }

  private List findEdges(String begin) {
    List 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 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 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. o ile długość na węźle docelowym nie wynosi Integer.MAX_VALUE to oznacza, iż 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 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();
      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 prawdopodobnie możemy przyspieszyć algorytm choćby bardziej przez preferowanie przeszukiwania nieodwiedzonych węzłów, które zostały odwiedzone przez najkrótszą ścieżkę.

private String getNext(List 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, iż 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ć, iż 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żeli tak, nie znalazłem ich.

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

Końcowy kod, który przez cały czas 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<>();
}
}
}