Skip to content

Instantly share code, notes, and snippets.

@xnnyygn
Last active December 29, 2015 12:49
Show Gist options
  • Save xnnyygn/7672947 to your computer and use it in GitHub Desktop.
Save xnnyygn/7672947 to your computer and use it in GitHub Desktop.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public class Dijkstra {
class VectorAndDistance {
int vector;
int distance;
VectorAndDistance(int vector, int distance) {
this.vector = vector;
this.distance = distance;
}
}
interface VectorDistanceSet {
boolean isEmpty();
VectorAndDistance removeMin();
void updateDistance(int vector, int newDistance);
int getDistance(int vector);
}
class SimpleVectorDistanceSet implements VectorDistanceSet {
private DistanceAndStatus[] elements;
private int size;
SimpleVectorDistanceSet(int vectorCount) {
if (vectorCount < 1)
throw new IllegalArgumentException("vector count must >= 1");
elements = new DistanceAndStatus[size = vectorCount];
for (int i = 0; i < size; i++) {
elements[i] = new DistanceAndStatus(Integer.MAX_VALUE, false);
}
}
public boolean isEmpty() {
return size == 0;
}
public VectorAndDistance removeMin() {
if (isEmpty()) throw new IllegalStateException("empty set");
int minDistance = Integer.MAX_VALUE;
int minVector = -1;
for (int i = 0; i < elements.length; i++) {
if (!elements[i].accessed && elements[i].distance <= minDistance) {
minDistance = elements[i].distance;
minVector = i;
}
}
elements[minVector].accessed = true;
size--;
return new VectorAndDistance(minVector, minDistance);
}
public void updateDistance(int vector, int newDistance) {
elements[vector] =
new DistanceAndStatus(newDistance, elements[vector].accessed);
}
public int getDistance(int vector) {
return elements[vector].distance;
}
}
class DistanceAndStatus {
int distance;
boolean accessed;
DistanceAndStatus(int distance) {
this(distance, true);
}
DistanceAndStatus(int distance, boolean accessed) {
this.distance = distance;
this.accessed = accessed;
}
}
static class AdjacencyList {
// start -> [(end, weight)]
private Map<Integer, List<VectorAndWeight>> connection =
new HashMap<Integer, List<VectorAndWeight>>();
AdjacencyList(int[][] adjacencyList) {
for (int[] edge : adjacencyList) {
// start, end, weight
int startVector = edge[0];
if (!connection.containsKey(startVector)) {
connection.put(startVector, new ArrayList<VectorAndWeight>());
}
connection.get(startVector).add(new VectorAndWeight(edge[1], edge[2]));
}
}
List<Integer> getEndVectorFrom(int startVector) {
List<Integer> vectors = new ArrayList<Integer>();
if (connection.containsKey(startVector)) {
for (VectorAndWeight item : connection.get(startVector)) {
vectors.add(item.vector);
}
}
return vectors;
}
int weight(int startVector, int endVector) {
if (connection.containsKey(startVector)) {
for (VectorAndWeight item : connection.get(startVector)) {
if (item.vector == endVector) return item.weight;
}
}
throw new IllegalArgumentException("no edge between vector ["
+ startVector + "] and vector [" + endVector + "]");
}
}
static class VectorAndWeight {
int vector;
int weight;
VectorAndWeight(int vector, int weight) {
this.vector = vector;
this.weight = weight;
}
}
/**
* Find minimum distance in adjacency list from start vector to end one.
*
* @param adjacencyList
* @param vectorCount
* @param startVector
* @param endVector
*/
public void findMinDistance(AdjacencyList adjacencyList, int vectorCount,
int startVector, int endVector) {
VectorDistanceSet distanceSet = new SimpleVectorDistanceSet(vectorCount);
int[] previousLink = new int[vectorCount];
distanceSet.updateDistance(startVector, 0);
while (!distanceSet.isEmpty()) {
VectorAndDistance vd = distanceSet.removeMin();
int u = vd.vector;
for (int v : adjacencyList.getEndVectorFrom(u)) {
int weight = adjacencyList.weight(u, v);
if (distanceSet.getDistance(v) > vd.distance + weight) {
distanceSet.updateDistance(v, vd.distance + weight);
previousLink[v] = u;
}
}
if (u == endVector) break;
}
int minDistance = distanceSet.getDistance(endVector);
System.out.println(minDistance);
if (minDistance == Integer.MAX_VALUE) return;
printPath(startVector, endVector, previousLink);
}
private void printPath(int startVector, int endVector, int[] previousLink) {
LinkedList<Integer> stack = new LinkedList<Integer>();
stack.push(endVector);
int vx = endVector;
while (previousLink[vx] != startVector) {
stack.push(previousLink[vx]);
vx = previousLink[vx];
}
stack.push(startVector);
System.out.println(stack);
}
public static void main(String[] args) {
AdjacencyList adjacencyList = new AdjacencyList(new int[][] {
{0, 1, 6},
{0, 2, 3},
{1, 2, 2},
{1, 3, 5},
{2, 3, 3},
{2, 4, 4},
{3, 4, 2},
{3, 5, 3},
{4, 5, 5}
});
Dijkstra dijkstra = new Dijkstra();
dijkstra.findMinDistance(adjacencyList, 6, 0, 5);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment