dijkstra.java

简单的dijkstra最短路径算法

import java.io.*;
import java.util.*;

public class Dijkstra {

	//vertice inicial
	private static String u;
	//conjunto auxiliar T de vertices
	private static ArrayList T = new ArrayList();
	//infinito
	private static final int infi = 100000000;
	//conjunto V de vertices
	private static ArrayList V = new ArrayList();
	//Matriz de adjacencia [lin][col] , -1 senao existe aresta e > -1 = peso
	private static long mAdj[][];
	//distancia de u a v, L[] sincronizado com V
	private static long L[];


	//---------------------------------------------------------------

	public static void main(String args[]) {
			readFile("g1.txt");
			//printMAdj();
			run("a", false);
	}

	//---------------------------------------------------------------

	private static void readFile(String fname)   {

			try{

					RandomAccessFile raf = new RandomAccessFile(fname, "r");
					byte[] b = new byte[(int)raf.length()];
					raf.read(b);
				    raf.close();
				    //arquivo todo lido pra dentro de s
					String s = new String(b);
					//vertices A, B, C ...
					String Vert = s.substring(0, s.indexOf("/")-1).trim();
					//preenche V
					parseV(Vert);
					//arestas AB, AC, ...
					String Edges = s.substring(s.indexOf("/")+1).trim();
					//preenche matriz de adjacencias
					parseE(Edges);

		    }
		     catch (FileNotFoundException e){
			  System.out.println("erro: Arquivo " + fname + " n鉶 encontrado ");
			}
			catch (IOException e) {
			 System.out.println("erro: " + e);
		    }
		    catch (IndexOutOfBoundsException e) {
			 System.out.println("Arquivo " + fname + " invalido.");
			}


	}

	//---------------------------------------------------------------

	//recebe string de vertices e seta V
	private static void parseV(String vert) {

		int i=0;
		String aux = new String("");
		while (i < vert.length()) {

			if (vert.charAt(i) != ',')
				aux += vert.charAt(i);
			else {
				V.add(aux.trim());
				aux = "";
			}

			i++;
		}

		V.add(aux.trim());
	}

	//---------------------------------------------------------------

	//recebe string de arestas e seta matriz de adj
	private static void parseE(String arestas) {

		//inicializa matriz de adjacencias com dimensao nxn
		mAdj = new long[V.size()][V.size()];

		//inicializa
		for (int x=0; x < V.size(); x++)
			for (int y=0; y < V.size(); y++)
					mAdj[x][y] = infi;

		int i=0;
		String aux = new String("");
		int r, s, p;

		while (i < arestas.length()) {

			if (arestas.charAt(i) != '\n')
				aux += arestas.charAt(i);
			else{
				//aux contem "v1-v2=p"
				aux = aux.trim();
				//posicao de v1 em V
				r = V.indexOf(aux.substring(0, aux.indexOf('-')).trim());
				//posicao de v2 em V
				s = V.indexOf(aux.substring(aux.indexOf('-')+1, aux.indexOf('=')).trim());
				//peso p de v1 para v2
				p = Integer.parseInt(aux.substring(aux.indexOf('=')+1).trim());
				//marca aresta (v1, v2) em mAdj
				mAdj[r][s] = p;
				aux = "";
			}

			i++;
		}

			aux = aux.trim();
			//posicao de v1 em V
			r = V.indexOf(aux.substring(0, aux.indexOf('-')).trim());
			//posicao de v2 em V
			s = V.indexOf(aux.substring(aux.indexOf('-')+1, aux.indexOf('=')).trim());
			//peso p de v1 para v2
			p = Integer.parseInt(aux.substring(aux.indexOf('=')+1).trim());
			//marca aresta (v1, v2) em mAdj
			mAdj[r][s] = p;

	}


	//---------------------------------------------------------------

	//imprime a matriz de adj
	private static void printMAdj(){
			for (int i=0; i < V.size(); i++) {
				System.out.println('\n');
				for (int j=0; j < V.size(); j++)
					if (mAdj[i][j] != infi)
						System.out.print(" " + mAdj[i][j]);
					else
						System.out.print(" " + "-");
			}

			System.out.print("\n");
	}


	//---------------------------------------------------------------

	//calcula o L(v)
	private static boolean buildL() {

		try {
		//posicao de u na matriz de adj
		int pos = V.indexOf(u);
		//L tem dimensao n
		L = new long[V.size()];

		for (int i=0; i < V.size(); i++)
					L[i] = mAdj[pos][i];

		//L(u)
		L[pos] = 0;
		}
		catch (IndexOutOfBoundsException e) {
			System.out.println(u + " nao esta em V");
			return false;
		}

		return true;

	}

	//---------------------------------------------------------------


	//imprime L(v)
	private static void printL() {
		System.out.print("\n");
		for (int i=0; i < V.size(); i++) {
			if (L[i] != infi)
				System.out.print(" " + L[i]);
			else
				System.out.print(" -");
		}
	}

	//imprime L(v)
	private static void printL2() {
		System.out.print("\n");
			for (int i=0; i < V.size(); i++)
				if (L[i] != infi)
					System.out.println("L(" + V.get(i) + ")= " + L[i]);
				else
					System.out.println("L(" + V.get(i) + ")= infi");
	}

	//---------------------------------------------------------------

	//executa o algo de dijkstra
	private static void run(String vInicial, boolean debug) {

		System.out.println("Distancia a partir de " + vInicial);

		u = vInicial;

		//constroi L(v)
		if (!buildL()) return;

		T.add(u); // T <- {u}

		if (debug)
			for (int k=0; k < V.size(); k++)
				System.out.print(" " + V.get(k));


		while (!T.containsAll(V)) {
			if (debug) printL();
			String vLinha = findMinL();
			T.add(vLinha);
			updateL(vLinha);
		}

		if (debug)
			System.out.println("\nfim");
		else
			printL2();


	}

	//---------------------------------------------------------------

	private static void printV() {
		System.out.print("\n");
		for (int k=0; k < V.size(); k++)
			System.out.print(" " + V.get(k));

	}

	private static void printT() {
		System.out.print("\n");
		for (int k=0; k < T.size(); k++)
			System.out.print(" " + T.get(k));
	}


	//---------------------------------------------------------------

	private static void updateL(String vLinha) {

		int i;
		//V2 = V
		ArrayList V2 = new ArrayList(V);

		//remove T de V = V2
		for (i=0; i < T.size(); i++)
			V2.remove(V2.indexOf(T.get(i)));


		for (i=0; i < V2.size(); i++) {
			String vaux = (String)V2.get(i);
			long w = L[V.indexOf(vLinha)] + mAdj[V.indexOf(vLinha)][V.indexOf(vaux)];

			if  (w < L[V.indexOf(vaux)])
				L[V.indexOf(vaux)] = w;
		}

	}



	//---------------------------------------------------------------
	//retorna v nao pertencente a T tal que L(v)