Sparwdzenie poprawności algorytmu Dijkstry w Javie

Witam!

Pobrałem implementację algorytmy dijkstry skądś z internetu. Podobno działa, ale sprawdzam i jest problem. Kolejność dodawania krawędzi grafu wpływa na to czy algorytm znajdzie w ogóle drogę do jakiegoś wierzchołka. Proszę zwrócić uwagę na komentarz w linii nr 20. Całość można wrzucić do IDE i odpalić. Proszę, niech ktoś zerknie co jest tam źle.

import java.util.HashMap;
import java.util.Map;
import java.util.NavigableSet;
import java.util.TreeSet;

public class Dijkstra {
	private static final Graph.Edge[] GRAPH = {
			new Graph.Edge( "1", "3", 4 ),
			new Graph.Edge( "2", "3", 1 ),
			new Graph.Edge( "2", "5", 3 ),
			new Graph.Edge( "3", "5", 2 ),
			new Graph.Edge( "3", "6", 5 ),
			new Graph.Edge( "4", "5", 1 ),
			new Graph.Edge( "4", "7", 1 ),
			new Graph.Edge( "5", "6", 1 ),
			new Graph.Edge( "5", "7", 6 ),
			new Graph.Edge( "5", "8", 2 ),
			new Graph.Edge( "7", "9", 3 ),
			new Graph.Edge( "7", "9", 2 ),
			new Graph.Edge( "10", "3", 1 ), // GDY TO DAM JAK PIERWSZA KRAWEDZ (PZRESUNE NA POCZATEK) TO WSZYSTKO DZIALA - DLACZEGO?
	};
	private static final String START = "1";
	private static final String END = "0";

	public static void main( String[] args ) {
		Graph g = new Graph( GRAPH );
		g.dijkstra( START );
		g.printAllPaths();
		// g.printAllPaths();
	}
}

class Graph {
	private final Map<String, Vertex> graph; // mapping of vertex names to
												// Vertex objects, built from a
												// set of Edges

	/** One edge of the graph (only used by Graph constructor) */
	public static class Edge {
		public final String v1, v2;
		public final int dist;

		public Edge( String v1, String v2, int dist ) {
			this.v1 = v1;
			this.v2 = v2;
			this.dist = dist;
		}
	}

	/** One vertex of the graph, complete with mappings to neighbouring vertices */
	public static class Vertex implements Comparable<Vertex> {
		public final String name;
		public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
		public Vertex previous = null;
		public final Map<Vertex, Integer> neighbours = new HashMap<>();

		public Vertex( String name ) {
			this.name = name;
		}

		private void printPath() {
			if ( this == this.previous ) {
				System.out.printf( "%s", this.name );
			} else if ( this.previous == null ) {
				System.out.printf( "%s(unreached)", this.name );
			} else {
				this.previous.printPath();
				System.out.printf( " -> %s(%d)", this.name, this.dist );
			}
		}

		@Override
		public int compareTo( Vertex other ) {
			return Integer.compare( this.dist, other.dist );
		}
	}

	/** Builds a graph from a set of edges */
	public Graph( Edge[] edges ) {
		this.graph = new HashMap<>( edges.length );

		// one pass to find all vertices
		for ( Edge e : edges ) {
			if ( !this.graph.containsKey( e.v1 ) )
				this.graph.put( e.v1, new Vertex( e.v1 ) );
			if ( !this.graph.containsKey( e.v2 ) )
				this.graph.put( e.v2, new Vertex( e.v2 ) );
		}

		// another pass to set neighbouring vertices
		for ( Edge e : edges ) {
			this.graph.get( e.v1 ).neighbours.put( this.graph.get( e.v2 ), e.dist );
			this.graph.get( e.v2 ).neighbours.put( this.graph.get( e.v1 ), e.dist ); // undirected
																						// graph
		}
	}

	/** Runs dijkstra using a specified source vertex */
	public void dijkstra( String startName ) {
		if ( !this.graph.containsKey( startName ) ) {
			System.err.printf( "Graph doesn't contain start vertex \"%s\"\n", startName );
			return;
		}
		final Vertex source = this.graph.get( startName );
		NavigableSet<Vertex> q = new TreeSet<>();

		// set-up vertices
		for ( Vertex v : this.graph.values() ) {
			v.previous = v == source ? source : null;
			v.dist = v == source ? 0 : Integer.MAX_VALUE;
			q.add( v );
		}

		this.dijkstra( q );
	}

	/** Implementation of dijkstra's algorithm using a binary heap. */
	private void dijkstra( final NavigableSet<Vertex> q ) {
		Vertex u, v;
		while ( !q.isEmpty() ) {

			u = q.pollFirst(); // vertex with shortest distance (first iteration
								// will return source)
			if ( u.dist == Integer.MAX_VALUE )
				break; // we can ignore u (and any other remaining vertices)
						// since they are unreachable

			// look at distances to each neighbour
			for ( Map.Entry<Vertex, Integer> a : u.neighbours.entrySet() ) {
				v = a.getKey(); // the neighbour in this iteration

				final int alternateDist = u.dist + a.getValue();
				if ( alternateDist < v.dist ) { // shorter path to neighbour
												// found
					q.remove( v );
					v.dist = alternateDist;
					v.previous = u;
					q.add( v );
				}
			}
		}
	}

	/** Prints a path from the source to the specified vertex */
	public void printPath( String endName ) {
		if ( !this.graph.containsKey( endName ) ) {
			System.err.printf( "Graph doesn't contain end vertex \"%s\"\n", endName );
			return;
		}

		this.graph.get( endName ).printPath();
		System.out.println();
	}

	/**
	 * Prints the path from the source to every vertex (output order is not
	 * guaranteed)
	 */
	public void printAllPaths() {
		for ( Vertex v : this.graph.values() ) {
			v.printPath();
			System.out.println();
		}
	}
}