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