class Arc
{
public var weight = 0;
public var startNode = null;
public var endNode = null;
function Arc(startNode, endNode, weight)
{
if (weight > 0)
this.weight = weight;
else
print("Arc Length negative");
this.startNode = startNode;
this.endNode = endNode;
}
}
class Node
{
public var name = null;
public var order = null;
public var pLabel = null;
public var tLabel = null;
function Node(name)
{
this.name = name;
}
}
class Graph
{
public var nodes = [];
public var arcs = [];
public var results = [];
function addNode(name = None, node = None)
{
if (node == None)
node = Node(name);
nodes[node.name] = (node);
return node.name;
}
function addNodes(nodeList)
{
for( name in nodeList)
{
var node = Node(name);
self.nodes[node.name] = (node);
}
}
function addArc(startNode = None, endNode = None, weight = None, arc = None)
{
if (arc == None)
arc = Arc(startNode, endNode, weight);
self.arcs.append(arc);
return arc;
}
function addArcs(arcList)
{
for (startNode, endNode, weight) in arcList:
arc = Arc(startNode, endNode, weight)
self.arcs.append(arc)
}
function dijkstra(startNode, endNode)
{
current = startNode;
order = 1;
self.nodes[current].pLabel = 0;
self.nodes[current].order = order;
order += 1;
while (self.nodes[endNode].pLabel == None)
{
for (arc in self.arcs)
{
if (arc.startNode == current)
{
if (self.nodes[arc.endNode].pLabel == None)
{
if (not self.nodes[current].tLabel == None)
newTLabel = self.nodes[current].tLabel + arc.weight;
else
newTLabel = arc.weight;
if (newTLabel < self.nodes[arc.endNode].tLabel or self.nodes[arc.endNode].tLabel == None)
self.nodes[arc.endNode].tLabel = newTLabel;
}
}
else if arc.endNode == current:
if self.nodes[arc.startNode].pLabel == None:
if not self.nodes[current].tLabel == None:
newTLabel = self.nodes[current].tLabel + arc.weight
else:
newTLabel = arc.weight
if newTLabel < self.nodes[arc.startNode].tLabel or self.nodes[arc.startNode].tLabel == None:
self.nodes[arc.startNode].tLabel = newTLabel
}
lowest = None
for name in self.nodes.iterkeys()
{
if (self.nodes[name].pLabel == None)
{
if (not self.nodes[name].tLabel == None)
{
if lowest
{
if (self.nodes[name].tLabel < self.nodes[lowest].tLabel)
lowest = name;
}
else
lowest = name;
}
}
}
self.nodes[lowest].pLabel = self.nodes[lowest].tLabel;
self.nodes[lowest].order = order;
order += 1;
current = lowest;
}
current = endNode;
done = False;
while done == False:
for arc in self.arcs:
if arc.startNode == current:
if not self.nodes[arc.endNode].pLabel == None:
if arc.weight+self.nodes[arc.endNode].pLabel == self.nodes[current].pLabel:
current = arc.endNode;
self.results.append(arc);
else if arc.endNode == current:
if not self.nodes[arc.startNode].pLabel == None:
if arc.weight+self.nodes[arc.startNode].pLabel == self.nodes[current].pLabel:
current = arc.startNode;
self.results.append(arc);
if current == startNode:
done = True;
self.results.reverse();
return (self.nodes[endNode].pLabel, self.results)
}
}