title: Bus Routes Algorithm
body: <p>I'm trying to solve the following question:
  <a href="https://leetcode.com/problems/bus-routes/" rel="nofollow noreferrer">https://leetcode.com/problems/bus-routes/</a></p>
  <blockquote>
  <p>We have a list of bus routes. Each <code>routes[i]</code> is a bus route that the i<sup>th</sup> bus repeats forever. For example if <code>routes[0] = [1, 5, 7]</code>, this means that the first bus (0<sup>th</sup> indexed) travels in the sequence 1→5→7→1→5→7→1→... forever.</p>
  <p>We start at bus stop <code>S</code> (initially not on a bus), and we want to go to bus stop <code>T</code>. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.</p>
  <h2>Example:</h2>
  <h3>Input:</h3>
  <pre><code>routes = [[1, 2, 7], [3, 6, 7]]
  S = 1
  T = 6
  </code></pre>
  <h3>Output:</h3>
  <pre><code>2
  </code></pre>
  <h2>Explanation:</h2>
  <p>The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.</p>
  <h2>Note:</h2>
  <pre><code>1 &lt;= routes.length &lt;= 500.
  1 &lt;= routes[i].length &lt;= 500.
  0 &lt;= routes[i][j] &lt; 10 ^ 6.
  </code></pre>
  </blockquote>
  <p>My idea is to treat each stop as a Node. Each node has a color (the bus number), and has a value (the stop number).</p>
  <p>This problem would then be converted to a 0-1 BFS shortest path problem.</p>
  <p>Here's my code :</p>
  <pre class="lang-java prettyprint-override"><code>class Node {
    int val;
    int color;
    boolean visited;
    int distance;
  
    public Node(int val, int color) {
      this.val = val;
      this.color = color;
      this.visited = false;
      this.distance = 0;
    }
  
    public String toString() {
      return &quot;{ val = &quot; + this.val  +  &quot;, color = &quot; + this.color + &quot; ,distance = &quot; + this.distance + &quot;}&quot;;
    }
  }
  
  class Solution {
      public int numBusesToDestination(int[][] routes, int S, int T) {
        if(S == T) return 0;
        // create nodes
        // map each values node(s)
        // distance between nodes of the same bus, have 0 distance
        // if you're switching buses, the distance is 1
        Map&lt;Integer, List&lt;Node&gt;&gt; adjacency = new HashMap&lt;Integer, List&lt;Node&gt;&gt;();
        int color = 0;
        Set&lt;Integer&gt; colorsToStartWith = new HashSet&lt;Integer&gt;();
        for(int[] route : routes) {
          for(int i = 0; i &lt; route.length - 1; i++) {
            int source = route[i];
            int dest = route[i + 1];
            adjacency.putIfAbsent(source, new ArrayList&lt;Node&gt;());
            adjacency.putIfAbsent(dest, new ArrayList&lt;Node&gt;());
            if(source == S) colorsToStartWith.add(color);
            adjacency.get(source).add(new Node(dest, color));
            adjacency.get(source).add(new Node(source, color));
          }
          if(route[route.length - 1] == S) colorsToStartWith.add(color);
          adjacency.putIfAbsent(route[route.length - 1], new ArrayList&lt;Node&gt;());
          adjacency.get(route[route.length - 1]).add(new Node(route[0], color));
          adjacency.get(route[route.length - 1]).add(new Node(route[route.length - 1], color));
          color++;
        }
  
        // run bfs
        int minDistance = Integer.MAX_VALUE;
        Deque&lt;Node&gt; q = new LinkedList&lt;Node&gt;();
        Node start = new Node(S, 0);
        start.distance = 1;
        q.add(start);
        boolean first = true;
        boolean found = false;
        while(!q.isEmpty()) {
          Node current = q.remove();
          current.visited = true;
          System.out.println(current);
          for(Node neighbor : adjacency.get(current.val)) {
            if(!neighbor.visited) {
              neighbor.visited = true;
              if(neighbor.color == current.color || current.val == neighbor.val || first) {
                q.addFirst(neighbor);
                neighbor.distance = current.distance;
              } else {
                q.addLast(neighbor);
                neighbor.distance = current.distance + 1;
              }
              if(neighbor.val == T) { 
                minDistance = Math.min(minDistance, neighbor.distance);
              }
            }
          }
          first = false;
        }
        return minDistance == Integer.MAX_VALUE ? -1  : minDistance;      
      }
  }
  </code></pre>
  <p>I'm not sure why this is wrong.</p>
  <p>The following test case fails :</p>
  <pre><code>Routes = [
      [12,16,33,40,44,47,68,69,77,78,82,86,97],
      [5,8,25,28,45,46,50,52,63,66,80,81,95,97],
      [4,5,6,14,30,31,34,36,37,47,48,55,56,58,73,74,76,80,88,98],
      [58,59],
      [54,56,78,96,98],
      [7,30,35,44,60,87,97],
      [3,5,57,88],
      [3,9,13,15,23,24,28,38,49,51,54,59,63,65,78,81,86,92,95],
      [2,7,16,20,23,46,55,57,93],
      [10,11,15,31,32,48,53,54,57,66,69,75,85,98],
      [24,26,30,32,51,54,58,77,81],
      [7,21,39,40,49,58,84,89],
      [38,50,57],
      [10,57],
      [11,27,28,37,55,56,58,59,81,87,97],
      [0,1,8,17,19,24,25,27,36,37,39,51,68,72,76,82,84,87,89],
      [10,11,14,22,26,30,48,49,62,66,79,80,81,85,89,93,96,98],
      [16,18,24,32,35,37,46,63,66,69,78,80,87,96],
      [3,6,13,14,16,17,29,30,42,46,58,73,77,78,81],
      [15,19,32,37,52,57,58,61,69,71,73,92,93]
  ]
  S = 6
  T = 30
  </code></pre>
  <p>What is the error in my code that makes this test fail?</p>