The program originates from my studies in Computer Science at Fernuniversität Hagen.
/**
* Kürzeste Wege in einem Graphen ermitteln
*/
public class Dijkstra
{
// grün = leere Menge
// gelb = ausgangselement
// distanz von v = 0
// so lange menge der gelben elemente nicht leer ist
// wähle das element aus den gelben elementen mit der geringsten Entfernung als w
// färbe w grün
// für alle nachfolger von w als wI
// wenn wI nicht gelb oder grün
// färbe die kante rot,
// färbe wI gelb; Distanz von wI ist distanz von w + kosten des übergangs von w zu wI
// sonst wenn wI gelb
// wenn distanz von wI kleiner als distanz von w + kosten des übergangs von w zu wI
// färbe die kante rot,
// färbe die bisher rote kante zu wI gelb
// dist(wI) = dist(w)+cost(w,wI)
// sonst
// färbe w, wI gelb
// sonst
// färbe w, wI gelb
private static final int N = 6;
enum Status
{
GRAY,
RED,
YELLOW,
GREEN;
}
static Node[] graph = new Node[N];
static double[] dist = new double[N];
static Node[] father = new Node[N];
static boolean[] green = new boolean[N];
static class Node
{
private char name;
private NodeLink successorLeft;
private NodeLink successorRight;
private Status status = Status.GRAY;
private int distance;
Node(final char c)
{
this.name = c;
}
public char getName()
{
return name;
}
public void setName(final char name)
{
this.name = name;
}
public NodeLink getSuccessorLeft()
{
return successorLeft;
}
public void setSuccessorLeft(final NodeLink successorLeft)
{
this.successorLeft = successorLeft;
}
public NodeLink getSuccessorRight()
{
return successorRight;
}
public void setSuccessorRight(final NodeLink successorRight)
{
this.successorRight = successorRight;
}
public Status getStatus()
{
return status;
}
public void setStatus(final Status status)
{
this.status = status;
}
public int getDistance()
{
return distance;
}
public void setDistance(final int distance)
{
this.distance = distance;
}
}
static class NodeLink
{
private int targetNodeIndex;
private int cost;
private Status status = Status.GRAY;
NodeLink(final int target, final int cost)
{
this.targetNodeIndex = target;
this.cost = cost;
}
public int getTargetNodeIndex()
{
return targetNodeIndex;
}
public void setTargetNodeIndex(final int targetNodeIndex)
{
this.targetNodeIndex = targetNodeIndex;
}
public int getCost()
{
return cost;
}
public void setCost(final int cost)
{
this.cost = cost;
}
public Status getStatus()
{
return status;
}
public void setStatus(final Status status)
{
this.status = status;
}
}
static class LinkIterator
{
private boolean leftVisited = false;
private boolean rightVisited = false;
private Node node;
LinkIterator(final Node node)
{
this.node = node;
}
public boolean hasNext()
{
return !leftVisited || !rightVisited;
}
public NodeLink getNext()
{
if (!leftVisited)
{
leftVisited = true;
return node.getSuccessorLeft();
}
if (!rightVisited)
{
rightVisited = true;
return node.getSuccessorRight();
}
return null;
}
}
public static void main(final String[] args)
{
initNodes();
dijkstra();
output();
}
private static void output()
{
for (int i = 0; i < graph.length; i++)
{
System.out.println(graph[i].getName() + ": " + graph[i].getDistance());
LinkIterator lit = new LinkIterator(graph[i]);
while (lit.hasNext())
{
NodeLink next = lit.getNext();
if (next != null && next.getStatus() == Status.RED)
{
System.out.println("Link to " + next.getTargetNodeIndex() + " Status " + next.getStatus() + " cost " + next.getCost());
}
}
}
}
private static void dijkstra()
{
Node v = graph[0];
v.setStatus(Status.YELLOW);
v.setDistance(0);
while (hasYellowNodes(graph))
{
Node w = getNearestYellow(graph);
w.setStatus(Status.GREEN);
LinkIterator lit = new LinkIterator(w);
while (lit.hasNext())
{
NodeLink next = lit.getNext();
if (next != null)
{
Node wI = graph[next.getTargetNodeIndex()];
if (wI.getStatus() != Status.YELLOW && wI.getStatus() != Status.GREEN)
{
next.setStatus(Status.RED);
wI.setStatus(Status.YELLOW);
wI.setDistance(w.getDistance() + next.getCost());
}
else if (wI.getStatus() == Status.YELLOW)
{
if ((w.getDistance() + next.getCost()) < wI.getDistance())
{
next.setStatus(Status.RED);
removeRedLink(graph, wI);
wI.setDistance(w.getDistance() + next.getCost());
}
else
{
next.setStatus(Status.YELLOW);
}
}
else
{
next.setStatus(Status.YELLOW);
}
}
}
}
}
private static void removeRedLink(final Node[] graph, final Node wI)
{
boolean removed = false;
for (int i = 0; i < graph.length; i++)
{
LinkIterator lit = new LinkIterator(graph[i]);
while (lit.hasNext())
{
NodeLink candidate = lit.getNext();
if (candidate.getStatus() == Status.RED && graph[candidate.getTargetNodeIndex()].getName() == wI.getName())
{
candidate.setStatus(Status.YELLOW);
removed = true;
break;
}
}
if (removed)
{
break;
}
}
}
private static Node getNearestYellow(final Node[] nodes)
{
Node result = null;
if (hasYellowNodes(nodes))
{
result = nodes[firstYellowNode(nodes)];
for (int i = firstYellowNode(nodes); i < nodes.length; i++)
{
if (nodes[i].getStatus() == Status.YELLOW && nodes[i].getDistance() < result.getDistance())
{
result = nodes[i];
}
}
}
return result;
}
private static boolean hasYellowNodes(final Node[] nodes)
{
boolean result = false;
if (nodes != null && nodes.length > 0)
{
for (int i = 0; i < nodes.length; i++)
{
if (nodes[i].getStatus() == Status.YELLOW)
{
result = true;
break;
}
}
}
return result;
}
private static int firstYellowNode(final Node[] nodes)
{
int result = -1;
if (nodes != null && nodes.length > 0)
{
for (int i = 0; i < nodes.length; i++)
{
if (nodes[i].getStatus() == Status.YELLOW)
{
result = i;
break;
}
}
}
return result;
}
private static void initNodes()
{
char c = 'A';
for (int i = 0; i < N; i++)
{
graph[i] = new Node(c++);
}
// 0 1 2 3 4 5
// A B C D E F
graph[0].setSuccessorLeft(new NodeLink(1, 30));
graph[0].setSuccessorRight(new NodeLink(5, 90));
graph[1].setSuccessorLeft(new NodeLink(2, 10));
graph[1].setSuccessorRight(new NodeLink(3, 40));
graph[2].setSuccessorLeft(new NodeLink(0, 40));
graph[2].setSuccessorRight(new NodeLink(5, 10));
graph[3].setSuccessorLeft(new NodeLink(4, 30));
graph[5].setSuccessorLeft(new NodeLink(4, 20));
}
}