Dijkstra shortest path

DijkstraDemo.java

import java.io.*;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Collections;

// Linkki kahden noden välillä

class Edge {
	private String fromNode, toNode;
	private double weight; // weight == etäisyys noiden kahden noden välillä
	
	public Edge( String from, String to, double w ){
		fromNode = from;
		toNode = to;
		weight = w;
		}
	
	public String get_from_node(){ return fromNode; }
	public String get_to_node(){ return toNode; }
	public Double get_weight(){ return new Double( weight ); }
	
	}


class Graph {
	ArrayList< Edge > edges;
	ArrayList< String > nodes;
	
	public Graph(){
		edges = new ArrayList<Edge>();
		nodes = new ArrayList<String>();
		}
	
	public void create_node( String node ){
		nodes.add( node );
		}
	public void connect( String nodeA, String nodeB, double weight ){
		edges.add( new Edge( nodeA, nodeB, weight ) );
		}
	
	public ArrayList<String> get_nodes(){ return nodes; }
	
	// etsitään kaikki edget, joissa from_node on haluttu
	public ArrayList<Edge> get_connected( String node ){
		ArrayList<Edge> out = new ArrayList<Edge>();
		
		for( int i = 0 ; i < edges.size() ; ++i ){
			if( edges.get(i).get_from_node() == node ){
				out.add( edges.get(i) );
				}
			}
		
		return out;
		}
	
	}


public class DijkstraDemo {



	// http://en.wikipedia.org/wiki/Dijkstra_algorithm#Pseudocode
	
	static public ArrayList<String> get_shortest_path( Graph graph, String start, String stop ){
		ArrayList<String> nodes = graph.get_nodes();
		ArrayList<String> Q = new ArrayList<String>();
		ArrayList<String> shortest_path = new ArrayList<String>();
		HashMap<String, Double> dist = new HashMap<String, Double>();
		HashMap<String, String> previous = new HashMap<String, String>();
		
		// merkataan ensin, että ei tiedetä mitään lyhyimmästä polusta tai etäisyyksistä
		for( String node : nodes ){
			dist.put( node, 1e99 ); // 10^99 on likimain ääretön :D
			previous.put( node, "" );
			Q.add( node );
			}
		
		// startissa etäisyys lähtöpisteestä lähtöpisteeseen on tietty nolla :D
		
		dist.put( start, 0.0 );
		
		// Niin kauan kuin tutkittavaa riittää
		while( Q.size() > 0 ){
			String nearest_node = new String();
			double smallest_distance = 1e99;
			
			for( String node : Q ){
				// Etsitään lyhyin etäisyys kahden noden välille
				if( dist.get( node ) < smallest_distance ){
					smallest_distance = dist.get( node );
					nearest_node = node;
					}
				} 
			if( smallest_distance > 1e90 || nearest_node == "" ){
				// nyt loppu eli ei löytynyt enää mitään läpikäytävää ts tultiin umpikujaan
				break;
				}
				
			// poistetaan tutkittavien listasta
			Q.remove( Q.indexOf( nearest_node ) );
			
			ArrayList<Edge> edges = graph.get_connected( nearest_node ); 
			
			// käydään läpi noita linkkejä, josko sieltä löytyis mihin kannattaa mennä seuraavaksi
			for( Edge edge : edges ){
				
				double alt = dist.get( nearest_node ) + edge.get_weight();
				
				// löytyi node, joka todennäköisesti kuuluu lyhyimpään reittiin
				if( alt < dist.get( edge.get_to_node() ) ){
					dist.put( edge.get_to_node(), alt );
					previous.put( edge.get_to_node(), edge.get_from_node() );
					}
				}
			
			}
		
		String position = stop;
		// haetaan se lyhyin polku (takaperin eli lopusta alkuun)
		while( previous.containsKey( position ) ){
			shortest_path.add( position );
			position = previous.get( position );
			}

		// koska polku on takaperin, flipataan se ympäri
		Collections.reverse( shortest_path );
		
		return shortest_path;
		}
	
	
	static public void main( String[] args ){
		//System.out.println( "Moi!" );
		
		Graph graafi = new Graph();
		
		/*
		 * A -> B 
		 * A -> C
		 * C -> D
		 * B -> E
		 * D -> E
		 * 
		 * A - B - E
		 * |       |
		 * C - D - -
		 * 
		 * Eli silloin tietty A -> E menee A, B, E
		 * Eikä A, C, D, E
		 * 
		 * */
		
		graafi.create_node( "A" );
		graafi.create_node( "B" );
		graafi.create_node( "C" );
		graafi.create_node( "D" );
		graafi.create_node( "E" );
		
		// laitetaan kaikki samanpituisiksi 
		graafi.connect( "A", "B", 1.0 ); 
		graafi.connect( "A", "C", 1.0 ); 
		graafi.connect( "C", "D", 1.0 ); 
		graafi.connect( "B", "E", 1.0 ); 
		graafi.connect( "D", "E", 1.0 ); 
		
		ArrayList<String> path = get_shortest_path( graafi, "A", "E" );
		
		System.out.print( "path = " );
		for( String node : path ){
			System.out.print( node + " " );
			}
		System.out.println("");
		}
	
	
	
	
	
	
	
	}