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