navigation.java

自己上学编的基于Dijkstra的最短路径&最大流量java源码

import java.io.*;
import java.util.StringTokenizer;
import java.util.Vector;

/**
 * The class Navigation finds the shortest (and/or) path between points
 * on a map using the Dijkstra algorithm
 * 
 * 
 * 
 *
 */
public class Navigation {
	/**
	 * Return codes:
	 * 		-1 if the source is not on the map
	 * 		-2 if the destination is not on the map
	 * 		-3 if both source and destination points are not on the map
	 * 		-4 if no path can be found between source and destination
	 */
	public static final int SOURCE_NOT_FOUND = -1;
	public static final int DESTINATION_NOT_FOUND = -2;
	public static final int SOURCE_DESTINATION_NOT_FOUND = -3;
	public static final int NO_PATH = -4;
	
	// to be set value if to find shortestDistance
	private int shortestDistance;
	
	// to be set value if to find fastestTime
	private float fastestTime;
	
	// A collection of edges
	private Vector<Kante> roads;
	
	// A collection of vertices
	private Vector<Knote> nodes;
	
	// compute results(a result represents each node together with its PreNode in the shortest path and the weight between them)  
	private Vector<Result> results;
	
	// selected vertices
	private Vector<String> groupA;
	
	// marginal vertices and not reached vertices(not_selected vertices)
	private Vector<String> groupB;
	
	// data represents the original text file
	private Vector<String> data;
	
	// source(start vertex)
	private String startNode;
	
	
	/**
	 * The constructor
	 * 
	 * @param filename name of the file containing the input map
	 */
	public Navigation(String  filename) {
		
		// initial collections
		this.roads = new Vector<Kante>();
		this.nodes = new Vector<Knote>();		 
		this.data = new Vector<String>();
		
        // read file
		try {
			FileReader fr = new FileReader(filename);
			BufferedReader in = new BufferedReader(fr);

			String line;
			while ((line = in.readLine()) != null) {
				data.add(line);
			}
			in.close();
			fr.close();
		} 
		catch (FileNotFoundException e) {
			e.printStackTrace();

		} 
		catch (IOException e) {
			e.printStackTrace();
		}
		
		// informations will save in local collections
		int i;
		String[] info;
		Kante kantetemp;
		Knote knotetemp;

		for (String s : data) {
			
			// pick up useful informations
			if(s.contains("label=")) {				
				StringTokenizer x;
				
				// pick up edges
				if(s.contains("->")) {
					info = new String[4];
					i = 0;
					
					// sprite string
					x = new StringTokenizer(s, " ->[label=\",];");
					while (x.hasMoreTokens()) {
						info[i++] = x.nextToken();						
					}
					
					// Dijkstra‘s Algorithm is only use to solve single source shortest path with arbitrary positive edge weights
					if(Integer.parseInt(info[2]) < 0 || Integer.parseInt(info[3]) < 0)
						System.out.println("negative edge weights between" + info[0] + "and" + info[1] + 
								", errors occurred if compute with Dijkstra‘s Algorithm!");
						
					kantetemp = new Kante(info[0], info[1], Integer.parseInt(info[2]), Integer.parseInt(info[3]));
					roads.add(kantetemp);
				}
				
				// pick up vertices
				else {
					info = new String[3];
					i = 0;
					
					// sprite string
					x = new StringTokenizer(s, " [label=\"];,");
					while (x.hasMoreTokens()) {
						info[i++] = x.nextToken();						
					}
					
					// warning if get negative wait time
					if(Integer.parseInt(info[2]) < 0)
						System.out.println("negative waittime of " + info[1] + ", no reasonable!");
					
					knotetemp = new Knote(info[0], Integer.parseInt(info[2]));
					nodes.add(knotetemp);
				}
			}
		}		
	}
	

	/**
	 * This methods finds the shortest route (distance) between
	 * points A and B on the map given in the constructor.
	 * 
	 * If a route is found the return value is an object of type Vector<String>,
	 * where every element is a String representing one line in the map. The
	 * output map is identical to the input map, apart from that all edges on the 
	 * shortest route are marked "bold". It is also possible to output a map
	 * where all shortest paths starting in A are marked bold.
	 *  
	 * The order of the edges as they appear in the output may differ from the input.
	 * 
	 * @param A Source
	 * @param B Destination
	 * @return returns a map as described above
	 * 		   if A or B is not on the map or if there is no path
	 * 		   between them the original map is to be returned.
	 */
	public Vector < String > findShortestRoute(String A, String B) {
		
		startNode = A;
		Vector < String > output = data;
		
		//if map is leer or lack edges informations, warning
		if(data == null || roads == null) {
			System.out.println("leer map or lack edges informations");
			return data;
		}
		
		if(!findNodeinRoads(A) && !findNodeinRoads(B))
			System.out.println("both SOURCE and DESTINATION are not found");
		else if(!findNodeinRoads(A))
			System.out.println("SOURCE is not found");
		else if(!findNodeinRoads(B))
			System.out.println("DESTINATION is not found");
		
		else {
			// initial selected vertices,add in the start vertex
			groupA = new Vector < String >();
			groupA.add(A);

	        // initial not_selected vertices, all vertices without start vertex
	        groupB = new Vector < String >();
	        for (Knote no : nodes)
	        	groupB.add(no.getName());
	        groupB.remove(A);      

	        // initial PreNodes of each vertex in the shortest path and the weight between them, -1 means no available path
	        results = new Vector<Result>();
	        results.add(new Result(A, A, 0));
	        for (String s : groupB) 
	        	results.add(new Result(A, s, getWeight_SD(A,s)));
	        

	        /* 
	         * Extract a vertex v from not_selected vertices to which there is a minimal edge  
	         * between selected vertices and not_selected vertices, then insert v in selected vertices
	         */
	        while (groupB.size() > 0) {
	        	 
	        	MiniPass mp = getMinSideNode_SD();
	        	
	        	/*
	        	 * if already found the the shortest route (distance) between given points A and B, update the map with 
	        	 * all edges on the shortest route are marked "bold".
	        	 */	        	
	        	if(mp.getLastNode().equals(B)) {
	        		Vector<String> routes = mp.getNodeList();
	        		this.shortestDistance = (int) mp.getWeight();
	        		
	        		// -1 means no available path, original map remains
	        		if(this.shortestDistance == -1) {
	                    routes.add(A);
	                    System.out.println();
	        		}
	        		
	        		
	        		else 
	        			if(routes.size() > 1) {
	        				String s1,s2;
	        				
		        			//mark all edges on the shortest route
		        			for (int i = 1 ; i < routes.size(); i++) {
		        				s1 = routes.elementAt(i-1);
		        				s2 = routes.elementAt(i);
		        				if(output != null) {
		        					String stemp;
		        					for(int j = 0 ; j < output.size(); j++) {
		        						stemp = output.elementAt(j);
		        						if(s1 != s2 && stemp.contains(s1) && stemp.contains(s2)) {
		        							stemp = stemp.substring(0, stemp.length() - 1);
		        							stemp = stemp + "[style=bold];";
		        							output.remove(j);
		        							output.add(j,stemp);
		        						}
		        					}
		        				}        				
		        			}
	        			}
	        	}
	            
	        	// insert node in selected vertices
	            String node = mp.getLastNode();
	            groupA.add(node); 
	            
	            /* 
	             * if because of inserting new point, lead to decrease minimum weight in not_selected vertices,reset minimum weight 
	             */
	            setWeight_SD(node);		
	        } 
		}
		return output;
	}
	
	/**
	 * This methods finds the fastest route (in time) between
	 * points A and B on the map given in the constructor.
	 * 
	 * If a route is found the return value is an object of type Vector<String>,
	 * where every element is a String representing one line in the map. The
	 * output map is identical to the input map, apart from that all edges on the 
	 * shortest route are marked "bold". It is also possible to output a map
	 * where all shortest paths starting in A are marked bold.
	 * 
	 * The order of the edges as they appear in the output may differ from the input.
	 * 
	 * @param A Source
	 * @param B Destination
	 * @return returns a map as described above
	 * 		   if A or B is not on the map or if there is no path
	 * 		   between them the original map is to be returned.
	 */
	public Vector < String > findFastestRoute(String A, String B) {
		
		startNode = A;
		Vector < String > output = data;
		
		//if map is leer or lack edges informations or lack vertices informations, warning
		if(data == null || roads == null || nodes == null) {
			System.out.println("leer map or lack edges informations or lack vertices informations");
			return data;
		}
		
		if(!findNodeinRoads(A) && !findNodeinRoads(B))
			System.out.println("both SOURCE and DESTINATION are not found");
		else if(!findNodeinRoads(A))
			System.out.println("SOURCE is not found");
		else if(!findNodeinRoads(B))
			System.out.println("DESTINATION is not found");
		
		else {
			
			// initial selected vertices,add in the start vertex
			groupA = new Vector < String >();
			groupA.add(A);
			
			// initial not_selected vertices, all vertices without start vertex
	        groupB = new Vector < String >();
	        for (Knote no : nodes)
	        	groupB.add(no.getName());
	        groupB.remove(A);  
	        
	        // initial PreNodes of each vertex in the shortest path and the weight between them, -1 means no available path
	        results = new Vector<Result>();
	        results.add(new Result(A, A, 0));
	        for (String s : groupB) 
	        	results.add(new Result(A, s, getWeight_FT(A,s)));
	        

	        /* 
	         * Extract a vertex v from not_selected vertices to which there is a minimal edge  
	         * between selected vertices and not_selected vertices, then insert v in selected vertices
	         */
	        while (groupB.size() > 0) {
	        	
	        	MiniPass mp = getMinSideNode_FT();
	        	
	        	/*
	        	 * if already found the the shortest route (distance) between given points A and B, update the map with 
	        	 * all edges on the shortest route are marked "bold".
	        	 */	 
	        	if(mp.getLastNode().equals(B)) {
	        		Vector<String> routes = mp.getNodeList();
	        		this.fastestTime = mp.getWeight();
	        		
	        		// -1 means no available path, original map remains
	        		if(this.fastestTime == -1) {
	                    routes.add(A);
	                    System.out.println();
	        		}

	        		if(routes.size() > 1) {
	        			String s1,s2;
	        			
	        			//mark all edges on the shortest route
	        			for (int i = 1 ; i < routes.size(); i++) {
	        				s1 = routes.elementAt(i-1);
	        				s2 = routes.elementAt(i);
	        				if(output != null) {
	        					String stemp;
	        					for(int j = 0 ; j < output.size(); j++) {
	        						stemp = output.elementAt(j);
	        						if(s1 != s2 && stemp.contains(s1) && stemp.contains(s2)) {
	        							stemp = stemp.substring(0, stemp.length() - 1);
	        							stemp = stemp + "[style=bold];";
	        							output.remove(j);
	        							output.add(j,stemp);