Dijkstra's algorithm in actionscript

[shizny]

class Dijkstra {   

private var visited:Array;
private var distance:Array;
private var previousNode:Array;
private var startNode:Number;
private var map:Array;
private var infiniteDistance:Number;
private var numberOfNodes:Number;
private var bestPath:Number;
private var nodesLeft:Array;
        
public function Dijkstra(ourMap:Array, startNode:Number, infiniteD:Number) {
    this.infiniteDistance = infiniteD;
    this.startNode = startNode;
    this.distance = new Array();
    this.previousNode = new Array();
    this.visited = new Array();
    this.map = ourMap;
    this.numberOfNodes = this.map[0].length;
    this.bestPath = 0;
    this.nodesLeft = new Array();
}

private function findShortestPath():Void {
    for (var i = 0; i < this.numberOfNodes; i++) {
         if (i == this.startNode) {
              this.visited[i] = 1;
              this.distance[i] = 0;
         }
         else {
              this.visited[i] = 0;
              this.distance[i] = this.map[this.startNode][i];
         }
         this.previousNode[i] = 0;
    }   
    while(this.somethingLeft(this.visited)) {
         this.nodesLeft = this.nodesNotVisited(this.visited);
         this.bestPath = this.findBestPath(this.distance, this.nodesLeft);
         this.updateDistanceAndPrevious(this.bestPath);
         this.visited[this.bestPath] = 1;
    }   
    this.getResults();
}

private function somethingLeft(ourVisited:Array):Boolean {
    for (var i = 0; i < this.numberOfNodes; i++) {
         if (!(ourVisited[i])) {
              return true;
         }
    }
    return false;
}

private function nodesNotVisited(ourVisited:Array):Array {
    var selectedArray = new Array();
    for (var i = 0; i < this.numberOfNodes; i++) {
         if (!(ourVisited[i])) {
              selectedArray.push(i);
         }
    }
    return selectedArray;
}

private function findBestPath(ourDistance:Array, ourNodesLeft:Array):Number {
    var bestPath = this.infiniteDistance;
    var bestNode = 0;
    for (var i = 0; i < ourNodesLeft.length; i++) {
         if (ourDistance[ourNodesLeft[i]] < bestPath) {
              bestPath = ourDistance[ourNodesLeft[i]];
              bestNode = ourNodesLeft[i];
         }
    }
    return bestNode;
}

private function updateDistanceAndPrevious(ourBestPath:Number):Void {
    for (var i = 0; i < this.numberOfNodes; i++) {
         if (!(this.map[ourBestPath][i] == this.infiniteDistance) || (this.map[ourBestPath][i] == 0)) {
              if ((this.distance[ourBestPath] + this.map[ourBestPath][i]) < this.distance[i]) {
                   this.distance[i] = this.distance[ourBestPath] + this.map[ourBestPath][i];
                   this.previousNode[i] = ourBestPath;
              }
         }
    }
}

private function getResults():Void {
    var ourShortestPath = new Array();
         for (var i = 0; i < this.numberOfNodes; i++) {
              ourShortestPath[i] = new Array();
              var endNode = null;
              var currNode = i;
              ourShortestPath[i].push(i);
              while(endNode != this.startNode) {
                   ourShortestPath[i].push(this.previousNode[currNode]);
                   endNode = this.previousNode[currNode];
                   currNode = this.previousNode[currNode];
              }
              ourShortestPath[i].reverse();
              trace("---------------------------------------");
              trace("The shortest distance from the startNode: "+this.startNode+
                    ", to node "+i+": is -> "+this.distance[i]);
              trace("The shortest path from the startNode: "+this.startNode+
                    ", to node "+i+": is -> "+ourShortestPath[i]);
              trace("---------------------------------------");
         }
    }
}

====Usage Example====
//Using a double scripted array as an adjacency matrix
rowZero = new Array(0, 1000000, 1000000, 1000000, 5, 12);
rowOne = new Array(15, 0, 9, 1000000, 1000000, 1000000);
rowTwo = new Array(1000000, 1000000, 0, 5, 1000000, 1000000);
rowThree = new Array(1000000, 2, 1000000, 0, 1000000, 1000000);
rowFour = new Array(1000000, 1000000, 10, 1000000, 0, 4);
rowFive = new Array(1000000, 1000000, 17, 20, 1000000, 0);

ourMap = new Array(rowZero, rowOne, rowTwo, rowThree, rowFour, rowFive);

var dijkstra = new Dijkstra(ourMap, 0, 1000000);
dijkstra.finsShortestPath();
====Done Usage Example====

[propaganja]

how do you use this scripts men...?can u elaborate and have an example how do you use these scripts..i badly need this bro...tnx a lot..thank you for posting this..thank uo bro.. more power

[Pulcinella]

This implementation will only find spanning tree for the node ID=0 in a fixed matrix. Which means if you say new Dijkstra(ourMap, 3, 1000000);, it will break - infinite loop in getResult while loop. Anyone has the brainpower, patience and time to modify this so it would work for any?

To run this, you can open a new Flash project (make sure its AS2), call it testing, copy the testing part to the code. Then open a new script file, call it Dijkstra, copy the rest of the code here, save, compile and run.

[shizny]

yeah, only works for startnode = 0 and then it will give you the shortest path from 0 to any other place in the matrix. Also, just found two typos in the example I posted.

In the usage example; instead of finsShortestPath() it should be findShortestPath

Also, you need to change the function findShortestPath to public from private.

I'd do a little work on figuring out how to go from any node to any other, but I don't have the time right now. You could always rearrange your matrix to work around the problem though

Sorry.

[propaganja]

thanks a lot...
can i ask another question bro..how about graphical representation of this..?do i need to make it a tile base type,or just a graph..? can u help me with this..coz i get confused here bro..i have been dying to make a routing planning...thanks bro..i admit im just a beginner in flash but im dying to learn.. thanks a lot bro..
hope u will have a patience in a novice..

[travikk]

Hey guys!

I took me few hours to code this, but my one is better one You can specify begining and end, works fully.
I hope Polish comments won't make you blind.

http://phpfi.com/305716

And here some usage:

var V:Array = new Array(0, 1, 2, 3, 4, 5, 6); // You should always numerate it like this, starting with 0. These are only IDs.
var E:Array = [
[], // this array shoould be empty, since it won't be used
[ [DESTINATION, LENGTH], [DESTINATION, LENGTH] ... ], // Each array in this one is a connection outgoing from vertex 1 to DESTIATION, which weights LENGTH
[ [DESTINATION, LENGTH], [DESTINATION, LENGTH] ... ], // Each array in this one is a connection outgoing from vertex 2 to DESTIATION, which weights LENGTH
...				
];

var dij:Dijkstra = new Dijkstra();
dij.setBegining( 6 ); // ID of begining. Remamber, that first one would be 1 NOT 0 !
dij.setEnd( 2 );
dij.setEdges( E );
dij.setVerticles( V );
dij.init();

[janebush08]

Thanks for the code ... travikk

[Blackened]

travik, the link you posted here is not working... could you help us by posting again the src here, or the correct link to it?

Thanks,

Bl.

[Phinrich]

Has anyone managed to re-code this EXCELENT Dijikstra so that theres some choice as to the start node and the end node ? I can select the end node but havent yet figured out how to select a start node other than 0 node. I would really appreciate any help in this regard.

Thanks