dijkstra.java

Easy implementation of PRIM and DIJKSTRA algorims for graph sorting. It also permit comparison of ti

import java.io.FileOutputStream;

public class Dijkstra {
  public class DijkstraResult {
  	public int P[];
  	public int D[];

  	public DijkstraResult(int vertices) {
  		D = new int [vertices];
  		P = new int [vertices];
  	}
  	
  	void SaveToFile(String File) {
  		try {
  			FileOutputStream oe = new FileOutputStream(File);
  			oe.write(new String("Nodo Origen:\t0\r\n").getBytes());
  			oe.write(new String("Caminos desde el resto de nodos al origen:\r\n").getBytes());

  			for(int i = 1; i < D.length; i++) {
  			  int ini = i;
  				oe.write(new String("[" + ini + "]").getBytes());
  				do {
  					oe.write(new String(" -- " + D[ini] + " --> [" + P[ini] + "]").getBytes());
  					ini = P[ini];
  				} while(ini != 0);
  				oe.write(new String("\r\n").getBytes());
  			}
  		} catch(Exception e) {}
  	}
  }
	
	public DijkstraResult DijkstraList(Grafo G) {
		DijkstraResult Result = new DijkstraResult(G.NumVertices);
	  boolean visited[] = new boolean [G.NumVertices]; // all false initially

		for(int i = 0; i < Result.D.length; i++) Result.D[i] = Integer.MAX_VALUE;
		Result.D[0] = 0;

		for(int i = 0; i < Result.D.length; i++) {
			int x = Integer.MAX_VALUE;
			int next = -1;
			for (int a = 0; a < Result.D.length; a++) {
				if (!visited[a] && Result.D[a] < x) {
					next = a;
					x = Result.D[a];
				}
			}
			visited[next] = true;
			for(int j = 0; j < G.NumVertices; j++) {
				Arista a = G.ObtenerArista(next, j);
				if(a == null) continue;
				int v = a.vertex2;
				int d = Result.D[next] + G.ObtenerArista(next, v).weight;
				if(Result.D[v] > d) {
					Result.D[v] = d;
					Result.P[v] = next;
				}
			}
		}
		return Result;
	}

	enum st {s, t};
	public DijkstraResult DijkstraHeap(Grafo G) {
		int i, j;
		int SPedgeCount = 0;
		OrdEntry smallest;
		st flag[]           = new st[G.NumVertices];
		OrdEntry changing   = new OrdEntry();
		int priority[]      = new int[G.NumVertices];
		DijkstraResult Result = new DijkstraResult(G.NumVertices);

		flag[0] = st.s;
		for(i = 1; i < G.NumVertices; i++) flag[i] = st.t;
		priority[0] = 0;
		for(i = 1; i < G.NumVertices; i++) priority[i] = Integer.MAX_VALUE;

		for(int n = 0; n < G.NumVertices; n++) {
			Arista a = G.ObtenerArista(0, n);
			if(a == null) continue;
			priority[a.vertex2] = a.weight;
			Result.P[a.vertex2] = 0;
		}

		MonticuloDijkstra heap = new MonticuloDijkstra(G.NumVertices, priority, G.NumVertices);
    priority = null;

		smallest = heap.extractMin();

		for(SPedgeCount = 0; SPedgeCount < G.NumVertices - 1; SPedgeCount++) {
			smallest = heap.extractMin();
			if(smallest.priority == Integer.MAX_VALUE) break;
			Result.D[smallest.id] = smallest.priority;
			flag[smallest.id] = st.s;
      for(j = 0; j < G.NumVertices; j++) {
      	Arista a = G.ObtenerArista(smallest.id, j);
      	if(a == null) continue;
				if (flag[a.vertex2] == st.t && smallest.priority + a.weight < heap.getPriority(a.vertex2)) {
					changing.id       = a.vertex2;
					changing.priority = smallest.priority + a.weight;
					heap.changePriority(changing);
					Result.P[a.vertex2] = smallest.id;
				}
		  }
		}
		if (SPedgeCount < G.NumVertices - 1) {
			for (i = 1; i < G.NumVertices; i++) {
				if (flag[i]==st.t) System.out.format("Vertex %d is not reachable from vertex 0\n",i);
			}
		}
		return Result;
	}	
	
	class MonticuloDijkstra {
		private int n; 
		private OrdEntry[] heap; 
		private int[] handle;

		public int left(int x) {
			return 2 * x;
		}

		public int right(int x) {
			return 2 * x + 1;
		}

		public int parent(int x) {
			return x / 2;
		}

		public boolean empty() {
			return n==0;
		}

		public void heapify(int j) {
			int best,r;
			OrdEntry entry = heap[j];

			while (true) {
				best=left(j);
				if (best>n) break;  
				r=right(j);
				if (r<=n && heap[best].priority>heap[r].priority) best=r;
				if (entry.priority<=heap[best].priority)  break;  
				heap[j]=heap[best];
				handle[heap[j].id]=j;
				j=best;
			}
			heap[j]=entry;
			handle[heap[j].id]=j;
		}

		public void swapUp(int j) {
			int p;
			OrdEntry entry = heap[j];

			p=parent(j);
			while (p>=1 && heap[p].priority>entry.priority) {
				heap[j]=heap[p];
				handle[heap[j].id]=j;
				j=p;
				p=parent(j);
			}

			heap[j] = entry;
			handle[heap[j].id]=j;
		}

		public int getPriority(int id) {
			return heap[handle[id]].priority;
		}

		public void changePriority(OrdEntry iEntry) {
			int i = handle[iEntry.id];

			if(iEntry.priority>heap[i].priority) {
				heap[i].priority=iEntry.priority;
				heapify(i);
			} else {
				heap[i].priority=iEntry.priority;
				swapUp(i);
			}
		}

		public OrdEntry extractMin() {
			OrdEntry returnEntry = heap[1];
			handle[heap[1].id] = -1;
			n--;
			if(empty()) return returnEntry;
			heap[1] = heap[n + 1];
			heapify(1);
			return returnEntry;
		}

		public MonticuloDijkstra(int capacity, int[] priorityIn, int count) {
			int i;
			heap   = new OrdEntry[capacity + 1];
			handle = new int[capacity];
			n      = count;

			for(i = 0; i < count; i++) {
				heap[i + 1]          = new OrdEntry();
				heap[i + 1].priority = priorityIn[i];
				heap[i + 1].id       = i;
				handle[i]            = i + 1;
			}
			for(; i < capacity; i++) handle[i]=(-1);
			for(i = parent(n); i > 0; i--) heapify(i);
		}
	}

	class OrdEntry {
		int priority;
		int id;
	}
}