Have you considered using virtual nodes with zero weighted edges to represent state transitions from your 0600 to your 1300 states at the same station? All nodes could have zero-weighted edges to virtual nodes at the same location, but with later times. I believe this would allow you to continue to use DFS with your existing edge.getWeight() call.