The Dijkstra class illustrates Dijkstra's algorithm for finding shortest paths
from a specified source vertex in a directed graph. The user is prompted to
select a vertex at which to begin. Negative edge weights are permitted, but may
cause the algorithm to fail. The set of permanently labeled vertices, denoted
S, is maintained by recoloring vertices to the color SColor. The d(.)
labels, which are used as tentative distances, are stored as the demand of each
vertex. For illustration purposes, it also seemed appropriate to display the
cut, which is used to identify the next permanently labeled
vertex.
The step() method divides the work into two logical steps. In the first step a vertex is added to S. In the second step, the d(.) labels are updated. Negative length cycles are detected by checking if the d(.) label of any vertex in S decreases.
package GraphStuff;
import MyUtil.*;
public final class Dijkstra extends GraphAlgorithm {
private int orgColorNum,SColorNum,cutColorNum,SCount,inf,step=1;
private boolean deliveredCannotFinish;
private Vertex v[], s, V;
private Edge[] e, Vedges;
private boolean p_completedInit=false;
public int GraphType() {return GraphPanel.Simple;}
public String title() {
return "Dijkstra's Algorithm for Finding Shortest Paths - directed";
}
static public final String failedInit = "Error: Cannot Initialize\n";
static public final String noEdges =
"This network has no edges, so there are no paths.\n";
static public final String noVertices =
"This network has no edges, so there are no paths.\n";
static public final String ready =
"Select a start vertex and press step to continue.\n";
static public final String description =
"This version of Dijkstra's Algorithm finds a shortest path tree from a "
+"selected vertex in a\n"
+"directed network. The algorithm may fail if any edge lengths are "
+"negative. This\n"
+"illustration colors the vertices in S and the edges in the [S,S'] cut. "
+"The number by\n"
+"each vertex is the tentative distance d(.), and initial distances "
+"represent infinity.\n";
static public final String cannotFinish =
"Because there are no edges in [S,S'], there are no paths to some vertices; "
+"however, the display\n"
+"shows the shortest path tree rooted at vertex `";
public boolean showLabels() {return true;}
public boolean showDemands() {return true;}
public boolean showWeights() {return true;}
public String init (GraphPanel gP) {
if (gP==null)
return failedInit;
Graph g = gP.graph;
if (g==null)
return failedInit;
if (g.numVertices()==0)
return noVertices;
if (g.numEdges()==0)
return noEdges;
deliveredCannotFinish=false;
orgColorNum=g.uncolor();
cutColorNum=orgColorNum+1;
SColorNum=orgColorNum+2;
e = g.edges();
inf=0;
for(int i=0;i<e.length;i++)
if (e[i].weight()>0)
inf+=e[i].weight();
inf+=1;
v = g.vertices();
for(int i=0;i<v.length;i++)
v[i].demand(inf);
SCount=0;
step=1;
p_completedInit=true;
return description + ready;
}
public String step(GraphPanel gP) {
if (gP==null)
return failedInit;
Graph g = gP.graph;
if (g==null || !p_completedInit)
return failedInit;
if (g.numVertices()==0)
return noVertices;
if (g.numEdges()==0)
return noEdges;
if (deliveredCannotFinish)
return null;
String ret=null;
if (step==1) {
if (SCount>=v.length)
return null; // already finished
if (SCount==0) {
s=null;
for(int i=0;i<v.length && s==null;i++) {
if (v[i].beenSelected()) {
s=v[i];
s.beenSelected(false);
break;
}
}
if (s==null)
s=v[0];
s.colorNum(SColorNum);
s.demand(0);
V=s;
} else {
int bestDist=inf, bestI=-1;
for(int i=0;i<e.length;i++) {
if (e[i].colorNum()==cutColorNum
&& e[i].weight()+e[i].U().demand()<bestDist) {
bestDist=e[i].weight()+e[i].U().demand();
bestI=i;
}
}
if (bestI==-1) {
deliveredCannotFinish=true;
return cannotFinish + s.vName() +"'.";
}
V=e[bestI].V();
e[bestI].colorNum(SColorNum);
V.colorNum(SColorNum);
for(int i=0;i<e.length;i++) {
if (e[i].colorNum()==cutColorNum
&& e[i].V()==V) {
e[i].colorNum(orgColorNum);
}
}
}
Vedges = V.edges();
if (Vedges!=null)
for(int i=0;i<Vedges.length;i++) {
if (Vedges[i].V().colorNum()==orgColorNum)
Vedges[i].colorNum(cutColorNum);
}
step=2;
SCount++;
if (SCount==1)
return "We begin by adding vertex `"+V.vName()+"' to S. The display "
+"shows the [S,S'] cut.\n"
+"Now we need to adjust the d(.) of "
+" vertices to which `"+V.vName()+"' has edges.";
return "Because d("+V.vName()+")="+V.demand()+" was minimal in "
+"S', we added `"+V.vName()+"' to S.\n"+"The display shows the "
+"new [S,S'] cut.\nNow we adjust the d(.) of vertices to which `"
+V.vName()+"' has edges.";
} else {
Vedges = V.outEdges();
if (Vedges!=null)
for(int i=0;i<Vedges.length;i++) {
if (Vedges[i].V().colorNum()==orgColorNum) {
if (Vedges[i].V().demand()>V.demand()+Vedges[i].weight()) {
Vedges[i].V().demand(V.demand()+Vedges[i].weight());
if (ret==null)
ret=Vedges[i].V().vName();
else ret=ret+","+Vedges[i].V().vName();
}
} else if(Vedges[i].V().demand()>V.demand()+Vedges[i].weight())
return "Since `"+Vedges[i].V().vName()+"' is in S and d("
+Vedges[i].V().vName()
+") would decrease, this algorithm is inapropriate.";
}
step=1;
}
if (SCount>=v.length)
return "Since none of the d(.) need adjusting, the display shows a "
+"shortest path tree rooted at `"+s.vName()+"'.\n"
+"The d(.) are the distance from `"+s.vName()+"'.";
if (ret==null)
return "In this case, none of the d(.) need adjusting.";
return "Note that we adjusted d(.) for these vertices: "+ret;
}
}