Algorithmus von Dijkstra

GISWiki - Das freie Portal für Geoinformatik (GIS)
Wechseln zu: Navigation, Suche

Deutsch

Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen. Die Gewichte dürfen dabei nicht negativ sein. Für Graphen mit negativen Gewichten aber ohne negative Zyklen ist der Bellman-Ford-Algorithmus geeignet.

Für nicht zusammenhängende, ungerichtete Graphen kann der Abstand zu bestimmten Knoten auch unendlich sein, wenn ein Pfad zwischen Startknoten und diesen Knoten nicht existiert. Dasselbe gilt auch für gerichtete, nicht stark zusammenhängende Graphen.

Algorithmus

G bezeichnet den gewichteten Graphen mit V (engl. vertex) als Knotenmenge, E (engl. edge) als Kantenmenge und Kosten als Gewichtsfunktion. s ist der Startknoten, U (engl. unvisited) ist die Menge der noch zu bearbeitenden Knoten und z ist ggf. ein spezieller Zielknoten, bei dem abgebrochen werden kann, wenn seine Distanz zum Startknoten bekannt ist.

Nach Ende des Algorithmus enthält Distanz die Abstände aller Knoten zu s. In Vorgänger ist ein spannender Baum der von s aus ausgehenden minimalen Wege in Form eines In-Tree gespeichert.

Wird bei Erreichen von z abgebrochen (mit #optional gekennzeichet), so enthalten Distanz und Vorgänger diese Werte nur für alle zuvor betrachteten Knoten. Dies sind mindestens die, die kleineren Abstand als z zu s besitzen.

01  für jedes v aus V
02      Distanz(v) := unendlich, Vorgänger(v) := kein
03  Distanz(s) := 0, Vorgänger(s) := 'begin', U := V
04  M := EMPTYSET 
05  für jedes (s,v) aus E mit v aus U
06      Distanz(v) := Kosten(s,v) 
07      M := M UNION {v}
08      Vorgänger(v) := s
09
10  solange M nicht leer
11      wähle u aus M mit Distanz(u) minimal                               
12      M := M - {u}  
13      U := U - {u}                                              
14      wenn u = z dann STOP   # optional
15      für jedes (u,v) aus E mit v aus U
16          M := M UNION {v} 
17          wenn Distanz(u) + Kosten(u,v) < Distanz(v) dann
18              Distanz(v) := Distanz(u) + Kosten(u,v)
19              Vorgänger(v) := u

Grundlegende Konzepte und Verwandtschaften

Der Algorithmus gehört zur Klasse der Greedy-Algorithmen. Sukzessive wird der nächstbeste Knoten, der einen kürzesten Pfad besitzt (Zeile 06), in eine Ergebnismenge aufgenommen und aus der Menge der noch zu bearbeitenden Knoten entfernt (Zeile 07). Damit findet sich eine Verwandtschaft zur Breitensuche, die ebenfalls solch ein gieriges Verhalten aufweist.

Ein alternativer Algorithmus zur Suche kürzester Pfade, der sich dagegen auf das Optimalitätsprinzip von Bellman stützt, ist der Floyd-Warshall-Algorithmus. Das Optimalitätsprinzip besagt, dass, wenn der kürzeste Pfad von A nach C über B führt, der Teilpfad A B auch der kürzeste Pfad von A nach B sein muss.

Ein weiterer alternativer Algorithmus ist der [[de:A*-Algorithmus|]], der den Algorithmus von Dijkstra um eine Abschätzfunktion erweitert. Falls diese gewisse Eigenschaften erfüllt, kann damit der kürzeste Pfad unter Umständen schneller gefunden werden.


Berechnung eines Spannbaumes

Negative Kante sorgt für Unklarheiten bei Knoten a

Nach Ende des Algorithmus ist in Vorgänger ein spannender Baum der Komponente von s aus kürzesten Pfaden von s zu allen Knoten der Komponente verzeichnet. Dieser Baum ist jedoch nicht notwendigerweise auch minimal, wie die Abbildung zeigt:

Sei x eine Zahl größer 0. Minimal spannende Bäume sind entweder durch die Kanten {a,s} und {a,b} oder {b,s} und {a,b) gegeben. Die Gesamtkosten eines minimal spannenden Baumes betragen 2+x. Dijkstras Algorithmus liefert mit Startpunkt s die Kanten {a,s} und {b,s} als Ergebnis. Die Gesamtkosten dieses spannenden Baumes betragen 2+2x.

Die Berechnung eines minimalen Spannbaumes ist mit dem Algorithmus von Prim oder dem Algorithmus von Kruskal möglich.

Zeitkomplexität

Im Folgenden sei m die Anzahl der Kanten und n die Anzahl der Knoten. Der Algorithmus von Dijkstra muss n mal den nächsten minimalen Knoten u bestimmen (Zeilen 05 und 06). Eine Möglichkeit wäre jedes Mal diesen mittels Durchlaufen durch eine Knotenliste zu bestimmen. Die Laufzeit beträgt dann <math>O(n^2)</math>. Eine effizientere Möglichkeit zur Liste bietet die Verwendung der Datenstruktur Fibonacci-Heap. Die Laufzeit beträgt dann lediglich <math>O(m+n\cdot\log (n))</math>.

Anwendungen

Routenplaner sind ein prominentes Beispiel, bei dem dieser Algorithmus eingesetzt werden kann. Der Graph repräsentiert hier das Straßennetz, welches verschiedene Punkte miteinander verbindet. Gesucht ist die kürzeste Route zwischen zwei Punkten.

Dijkstras Algorithmus wird auch im Internet als Routing-Algorithmus in OSPF eingesetzt.

Siehe auch

Literatur

  • E. W. Dijkstra: A note on two problems in connexion with graphs. In: Numerische Mathematik. 1 (1959), S. 269–271

Weblinks

English

Dijkstra's algorithm, named after its discoverer, Dutch computer scientist Edsger Dijkstra, is an algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights.

For example, if the vertices of the graph represent cities and edge weights represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between two cities.

The input of the algorithm consists of a weighted directed graph G and a source vertex s in G. We will denote V the set of all vertices in the graph G. Each edge of the graph is an ordered pair of vertices (u,v) representing a connection from vertex u to vertex v. The set of all edges is denoted E. Weights of edges are given by a weight function w: E → [0, ∞]; therefore w(u,v) is the non-negative cost of moving from vertex u to vertex v. The cost of an edge can be thought of as (a generalization of) the distance between those two vertices. The cost of a path between two vertices is the sum of costs of the edges in that path. For a given pair of vertices s and t in V, the algorithm finds the path from s to t with lowest cost (i.e. the shortest path). It can also be used for finding costs of shortest paths from a single vertex s to all other vertices in the graph.

Description of the algorithm

The algorithm works by keeping for each vertex v the cost d[v] of the shortest path found so far between s and v. Initially, this value is 0 for the source vertex s (d[s]=0), and infinity for all other vertices, representing the fact that we do not know any path leading to those vertices (d[v]=? for every v in V, except s). When the algorithm finishes, d[v] will be the cost of the shortest path from s to v -- or infinity, if no such path exists. The basic operation of Dijkstra's algorithm is edge relaxation: if there is an edge from u to v, then the shortest known path from s to u (d[u]) can be extended to a path from s to v by adding edge (u,v) at the end. This path will have length d[u]+w(u,v). If this is less than the current d[v], we can replace the current value of d[v] with the new value.

Edge relaxation is applied until all values d[v] represent the cost of the shortest path from s to v. The algorithm is organized so that each edge (u,v) is relaxed only once, when d[u] has reached its final value.

The algorithm maintains two sets of vertices S and Q. Set S contains all vertices for which we know that the value d[v] is already the cost of the shortest path and set Q contains all other vertices. Set S starts empty, and in each step one vertex is moved from Q to S. This vertex is chosen as the vertex with lowest value of d[u]. When a vertex u is moved to S, the algorithm relaxes every outgoing edge (u,v).

Pseudocode

In the following algorithm, u := Extract_Min(Q) searches for the vertex u in the vertex set Q that has the least d[u] value. That vertex is removed from the set Q and returned to the user.

 1  function Dijkstra(G, w, s)
 2     for each vertex v in V[G]                        // Initializations
 3           d[v] := infinity
 4           previous[v] := undefined
 5     d[s] := 0
 6     S := empty set
 7     Q := set of all vertices
 8     while Q is not an empty set                      // The algorithm itself
 9           u := Extract_Min(Q)
10           S := S union {u}
11           for each edge (u,v) outgoing from u
12                  if d[v] > d[u] + w(u,v)             // Relax (u,v)
13                        d[v] := d[u] + w(u,v)
14                        previous[v] := u

If we are only interested in a shortest path between vertices s and t, we can terminate the search at line 9 if u = t.

Now we can read the shortest path from s to t by iteration:

1 S := empty sequence 
2 u := t
3 while defined u                                        
4       insert u to the beginning of S
5       u := previous[u]

Now sequence S is the list of vertices on the shortest path from s to t.

Running time

We can express the running time of Dijkstra's algorithm on a graph with m edges and n vertices as a function of m and n using the Big O notation.

The simplest implementation of the Dijkstra's algorithm stores vertices of set Q in an ordinary linked list or array, and operation Extract-Min(Q) is simply a linear search through all vertices in Q. In this case, the running time is O(n2).

For sparse graphs, that is, graphs with much less than n2 edges, Dijkstra's algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using a binary heap or Fibonacci heap as a priority queue to implement the Extract-Min function. With a binary heap, the algorithm requires O((m+n)log n) time, and the Fibonacci heap improves this to O(m + n log n).

Related problems and algorithms

The functionality of Dijkstra's original algorithm can be extended with a variety of modifications. For example, sometimes it is desirable to present solutions which are less than mathematically optimal. To obtain a ranked list of less-than-optimal solutions, the optimal solution is first calculated. A single edge appearing in the optimal solution is removed from the graph, and the optimum solution to this new graph is calculated. Each edge of the original solution is suppressed in turn and a new shortest-path calculated. The secondary solutions are then ranked and presented after the first optimal solution.

OSPF (open shortest path first) is a well known real-world implementation of Dijkstra's algorithm used in internet routing.

Unlike Dijkstra's algorithm, the Bellman-Ford algorithm can be used on graphs with negative edge weights, as long as the graph contains no negative cycle reachable from the source vertex s. (The presence of such cycles means there is no shortest path, since the total weight becomes lower each time the cycle is traversed.)

A related problem is the traveling salesman problem, which is the problem of finding the shortest path that goes through every vertex exactly once, and returns to the start. This problem is NP-hard; in other words, unlike the shortest path problem, it is unlikely to be solved by a polynomial-time algorithm.

If additional information is available that estimates the "distance" to the target, the A* algorithm can be used instead to cut down on the size of the subset of the graph which is explored.

Literatur / Literature

Weblinks

Code

Implementations in various programming languages of Dijkstra's algorithm.

C

<c>

void dodijkstra(int sr,int ds,int path[])
{
        struct node
	{
	  int pre;   /* Predecessor */
	  int length; /* Length between the nodes */
	  enum {perm,tent} label; /* Enumeration for permanent and tentative labels */
	}state[MAX];
	
	int i,k,min;
	struct node *p;
	/* Initialisation of the nodes aka First step of Dijkstra Algo */
	for(p=&state[0];p<&state[no_nodes];p++)
	{
           p->pre= -1;
	   p->length=INFTY;
	   p->label=tent;
	}
	state[ds].length=0; /* Destination length set to zero */
	state[ds].label=perm; /* Destination set to be the permanent node */
	k=ds; /* initial working node */
	/* Checking for a better path from the node k ? */
	do
	{
           for(i=0;i<no_nodes;i++)
	      {
		  if(dist[k][i]!=0 && state[i].label==tent)
		     {
			if((state[k].length+dist[k][i])<state[i].length)
			   {
			       state[i].pre=k;
			       state[i].length=state[k].length+dist[k][i];
		           }
		     }
	      }
             k=0;
             min=INFTY;
	      /* Find a node which is tentatively labeled and with minimum label */
	      for(i=0;i<no_nodes;i++)
	      {
		 if(state[i].label==tent && state[i].length<min)
		    {
			min=state[i].length;
			k=i;
		    }
	      }
	      state[k].label=perm;
	} while(k!=sr);
	
	i=0;
	k=sr;
	/* Print the path to the output array */
	do {path[i++]=k;k=state[k].pre;} while(k>=0);
	path[i]=k;
}

</c>

C++

<c>

#include < map>
#include <queue>
using namespace std;

#define X first
#define Y second

template <class Node, class Edge=int> class Dijkstra {
   public:
   Dijkstra() {}
   Dijkstra(const Node &n, const Edge &e=0) { push(n, e); }
   bool empty() const { return q.empty(); }
   void push(const Node &n, const Edge &e=0) {
      Iter it = m.find(n);
      if (it == m.end()) it = m.insert(make_pair(n, e)).X;
      else if (it->Y > e) it->Y = e;
      else return;
      q.push(make_pair(e, it));
   }
   const Node &pop() {
      cur = q.top().Y;
      do q.pop();
      while (!q.empty() && q.top().Y->Y < q.top().X);
      return cur->X;
   }
   const Edge &dist() const { return cur->Y; }
   void link(const Node &n, const Edge &e=1) { push(n, cur->Y + e); }

   private:
   typedef typename map<Node, Edge>::iterator Iter;
   typedef pair<Edge, Iter> Value;
   struct Rank : public binary_function<Value, Value, bool> {
      bool operator()(const Value& x, const Value& y) const {
         return x.X > y.X;
      }
   };
   map<Node, Edge> m;
   priority_queue<Value, vector<Value>, Rank> q;
   Iter cur;
};

// Example usage (nodes and edges are represented with ints)
int shortestDistance(int nodes, int startNode, int endNode, int **dists) {
   Dijkstra<int> dijkstra(startNode);
   while (!dijkstra.empty()) {
      int curNode = dijkstra.pop();
      if (curNode == endNode)
         return dijkstra.dist();
      for (int i = 0; i < nodes; i++)
         if (dists[curNode][i] >= 0) // "i" is a neighbor of curNode
            dijkstra.link(i, dists[curNode][i]); // add weighted edge
   }
   return -1; // No path found
}

</c>

Actionscript

<actionscript>

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.findShortestPath();
====Done Usage Example====

</actionscript>

Python

<python>

import sys
infinity = sys.maxint - 1

class Vertex(object):
    """A vertex in a graph, using adjacency list.
    
    'edges' is a sequence or collection of tuples (edges), the first element of
    which is a name of a vertex and the second element is the distance to that vertex.
    'name' is a unique identifier for each vertex, like a city name, an integer, a tuple of coordinates..."""

    def __init__(self, name, edges):
        self.name = name
        self.edges = edges

def ShortestPath(graph, source, dest):
    """Returns the shortest distance from source to dest and a list of traversed vertices, using Dijkstra's algorithm.
    
    Assumes the graph is connected."""
    
    distances = {}
    names = {}
    path = []
    for v in graph:
        distances[v.name] = infinity # Initialize the distances
        names[v.name] = v # Map the names to the vertices they represent
    distances[source.name] = 0 # The distance of the source to itself is 0
    dist_to_unknown = distances.copy() # Select the next vertex to explore from this dict
    last = source
    while last.name != dest.name:
        # Select the next vertex to explore, which is not yet fully explored and which 
        # minimizes the already-known distances.
        next = names[ min( [(v, k) for (k, v) in dist_to_unknown.iteritems()] )[1] ]
        for n, d in next.edges: # n is the name of an adjacent vertex, d is the distance to it
            distances[n] = min(distances[n], distances[next.name] + d)
            if n in dist_to_unknown:
                dist_to_unknown[n] = distances[n]
        last = next
        if last.name in dist_to_unknown: # Delete the completely explored vertex
            path.append(last.name)
            del dist_to_unknown[next.name]
    return distances[dest.name], path

</python>

PHP

<php> <?PHP class Dijkstra {

var $visited = array(); var $distance = array(); var $previousNode = array(); var $startnode =null; var $map = array(); var $infiniteDistance = 0; var $numberOfNodes = 0; var $bestPath = 0; var $matrixWidth = 0;

function Dijkstra(&$ourMap, $infiniteDistance) { $this -> infiniteDistance = $infiniteDistance; $this -> map = &$ourMap; $this -> numberOfNodes = count($ourMap); $this -> bestPath = 0; }

function findShortestPath($start,$to = null) { $this -> startnode = $start; for ($i=0;$i<$this -> numberOfNodes;$i++) { if ($i == $this -> startnode) { $this -> visited[$i] = true; $this -> distance[$i] = 0; } else { $this -> visited[$i] = false; $this -> distance[$i] = isset($this -> map[$this -> startnode][$i]) ? $this -> map[$this -> startnode][$i] : $this -> infiniteDistance; } $this -> previousNode[$i] = $this -> startnode; }

$maxTries = $this -> numberOfNodes; $tries = 0; while (in_array(false,$this -> visited,true) && $tries <= $maxTries) { $this -> bestPath = $this->findBestPath($this->distance,array_keys($this -> visited,false,true)); if($to !== null && $this -> bestPath === $to) { break; } $this -> updateDistanceAndPrevious($this -> bestPath); $this -> visited[$this -> bestPath] = true; $tries++; } }

function findBestPath($ourDistance, $ourNodesLeft) { $bestPath = $this -> infiniteDistance; $bestNode = 0; for ($i = 0,$m=count($ourNodesLeft); $i < $m; $i++) { if($ourDistance[$ourNodesLeft[$i]] < $bestPath) { $bestPath = $ourDistance[$ourNodesLeft[$i]]; $bestNode = $ourNodesLeft[$i]; } } return $bestNode; }

function updateDistanceAndPrevious($obp) { for ($i=0;$i<$this -> numberOfNodes;$i++) { if( (isset($this->map[$obp][$i])) && (!($this->map[$obp][$i] == $this->infiniteDistance) || ($this->map[$obp][$i] == 0 )) && (($this->distance[$obp] + $this->map[$obp][$i]) < $this -> distance[$i]) ) { $this -> distance[$i] = $this -> distance[$obp] + $this -> map[$obp][$i]; $this -> previousNode[$i] = $obp; } } }

function printMap(&$map) { $placeholder = ' %' . strlen($this -> infiniteDistance) .'d'; $foo = ; for($i=0,$im=count($map);$i<$im;$i++) { for ($k=0,$m=$im;$k<$m;$k++) { $foo.= sprintf($placeholder, isset($map[$i][$k]) ? $map[$i][$k] : $this -> infiniteDistance); } $foo.= "\n"; } return $foo; }

function getResults($to = null) { $ourShortestPath = array(); $foo = ; for ($i = 0; $i < $this -> numberOfNodes; $i++) { if($to !== null && $to !== $i) { continue; } $ourShortestPath[$i] = array(); $endNode = null; $currNode = $i; $ourShortestPath[$i][] = $i; while ($endNode === null || $endNode != $this -> startnode) { $ourShortestPath[$i][] = $this -> previousNode[$currNode]; $endNode = $this -> previousNode[$currNode]; $currNode = $this -> previousNode[$currNode]; } $ourShortestPath[$i] = array_reverse($ourShortestPath[$i]); if ($to === null || $to === $i) { if($this -> distance[$i] >= $this -> infiniteDistance) { $foo .= sprintf("no route from %d to %d. \n",$this -> startnode,$i); } else { $foo .= sprintf('%d => %d = %d [%d]: (%s).'."\n" , $this -> startnode,$i,$this -> distance[$i], count($ourShortestPath[$i]), implode('-',$ourShortestPath[$i])); } $foo .= str_repeat('-',20) . "\n"; if ($to === $i) { break; } } } return $foo; } } // end class ?>

</php>

Usage Example

<php>

<?php

// I is the infinite distance. define('I',1000);

// Size of the matrix $matrixWidth = 20;

// $points is an array in the following format: (router1,router2,distance-between-them) $points = array( array(0,1,4), array(0,2,I), array(1,2,5),

	array(1,3,5),

array(2,3,5), array(3,4,5), array(4,5,5), array(4,5,5), array(2,10,30), array(2,11,40), array(5,19,20), array(10,11,20), array(12,13,20), );

$ourMap = array();


// Read in the points and push them into the map

for ($i=0,$m=count($points); $i<$m; $i++) { $x = $points[$i][0]; $y = $points[$i][1]; $c = $points[$i][2]; $ourMap[$x][$y] = $c; $ourMap[$y][$x] = $c; }

// ensure that the distance from a node to itself is always zero // Purists may want to edit this bit out.

for ($i=0; $i < $matrixWidth; $i++) {

   for ($k=0; $k < $matrixWidth; $k++) {
       if ($i == $k) $ourMap[$i][$k] = 0;
   }

}


// initialize the algorithm class $dijkstra = new Dijkstra($ourMap, I,$matrixWidth);

// $dijkstra->findShortestPath(0,13); to find only path from field 0 to field 13... $dijkstra->findShortestPath(0);

// Display the results

echo '
';
echo "the map looks like:\n\n";
echo $dijkstra -> printMap($ourMap);
echo "\n\nthe shortest paths from point 0:\n";
echo $dijkstra -> getResults();
echo '
';

?>

</php>

Visual Basic 6

<vb>

   Option Explicit
   
   Const nodeCount As Integer = 9          'number of nodes - 1
   Type DijkEdge
       weight As Integer                   'distance from vertices that it is connected to
       destination As Integer              'name of vertice that it is connected to
   End Type
   
   Type Vertex
       connections(nodeCount) As DijkEdge  'hold information above for each connection
       numConnect As Integer               'number of connections - 1
       distance As Integer                 'distance from all other vertices
       isDead As Boolean                   'distance calculated
       name As Integer                     'name of vertice
   End Type
   Public Sub dijkstra_shortest_Path()
       Const infinity As Integer = 15000   'number that is larger than max distance
       Dim i As Integer                    'loop counter
       Dim j As Integer                    'loop counter
       Dim sourceP As Integer              'point to determine distance to from all nodes
       Dim inputData As String             'temp variable to ensure good data enterred
       Dim graph(nodeCount) As Vertex      'all inforamtion for each point (see Vertex declaration above)
       Dim nextP As Integer                'closest point that is not dead
       Dim min As Integer                  'distance of closest point not dead
       Dim outString As String             'string to display the output
       Dim goodSource As Boolean
       
       'user enters source point data and ensured that it is correct
       Do
           goodSource = True
           inputData = (InputBox("What is the source point: ", "Source Point between: 0 & " & nodeCount))
           If IsNumeric(inputData) Then
               sourceP = CInt(inputData)
               If sourceP > nodeCount Or sourceP < 0 Then
                   MsgBox "Source point must be between 0 & " & nodeCount & "."
                   goodSource = False
               End If
           Else
               MsgBox "Source point must be numeric and be between 0 & " & nodeCount & "."
               goodSource = False
           End If
       Loop While Not goodSource
       'get data so we can analyze the distances
       Call populateGraph(graph)
       'set default values to not dead and distances to infinity (unless distance is to itself)
       For i = 0 To nodeCount
           If graph(i).name = sourceP Then
               graph(i).distance = 0
               graph(i).isDead = False
           Else:
               graph(i).distance = infinity
               graph(i).isDead = False
           End If
       Next i
       For i = 0 To nodeCount
           min = infinity + 1
           'determine closest point that is not dead
           For j = 0 To nodeCount
               If Not graph(j).isDead And graph(j).distance < min Then
                   nextP = j
                   min = graph(j).distance
               End If
           Next j
           'calculate distances from the closest point & to all of its connections
           For j = 0 To graph(nextP).numConnect
               If graph(graph(nextP).connections(j).destination).distance > graph(nextP).distance + graph(nextP).connections(j).weight Then
                   graph(graph(nextP).connections(j).destination).distance = graph(nextP).distance + graph(nextP).connections(j).weight
               End If
           Next j
           'kill the value we just looked at so we can get the next point
           graph(nextP).isDead = True
       Next i
       'display the distance from the source point to all other points
       outString = ""
       For i = 0 To nodeCount
           outString = outString & "The distance between nodes " & sourceP & " and " & i & " is " & graph(i).distance & vbCrLf
       Next i
       MsgBox outString
   End Sub

</vb> ====Example Data==== for testing <vb>

   Private Sub populateGraph(vertexMatrix() As Vertex)
       'get data into graph matrix to determine distance from all points
       Dim i As Integer
       Dim j As Integer
              
       '0 connections
       vertexMatrix(0).name = 0
       vertexMatrix(0).numConnect = 3
       vertexMatrix(0).connections(0).destination = 1
       vertexMatrix(0).connections(1).destination = 2
       vertexMatrix(0).connections(2).destination = 6
       vertexMatrix(0).connections(3).destination = 7
       vertexMatrix(0).connections(0).weight = 10
       vertexMatrix(0).connections(1).weight = 15
       vertexMatrix(0).connections(2).weight = 30
       vertexMatrix(0).connections(3).weight = 50
       
       '1 connections
       vertexMatrix(1).name = 1
       vertexMatrix(1).numConnect = 3
       vertexMatrix(1).connections(0).destination = 0
       vertexMatrix(1).connections(1).destination = 3
       vertexMatrix(1).connections(2).destination = 4
       vertexMatrix(1).connections(3).destination = 9
       vertexMatrix(1).connections(0).weight = 10
       vertexMatrix(1).connections(1).weight = 16
       vertexMatrix(1).connections(2).weight = 5
       vertexMatrix(1).connections(3).weight = 40
       
       '2 connections
       vertexMatrix(2).name = 2
       vertexMatrix(2).numConnect = 3
       vertexMatrix(2).connections(0).destination = 0
       vertexMatrix(2).connections(1).destination = 7
       vertexMatrix(2).connections(2).destination = 8
       vertexMatrix(2).connections(3).destination = 9
       vertexMatrix(2).connections(0).weight = 15
       vertexMatrix(2).connections(1).weight = 33
       vertexMatrix(2).connections(2).weight = 18
       vertexMatrix(2).connections(3).weight = 60
   
       '3 connections
       vertexMatrix(3).name = 3
       vertexMatrix(3).numConnect = 1
       vertexMatrix(3).connections(0).destination = 1
       vertexMatrix(3).connections(1).destination = 4
       vertexMatrix(3).connections(0).weight = 16
       vertexMatrix(3).connections(1).weight = 22
       
       '4 connections
       vertexMatrix(4).name = 4
       vertexMatrix(4).numConnect = 2
       vertexMatrix(4).connections(0).destination = 1
       vertexMatrix(4).connections(1).destination = 3
       vertexMatrix(4).connections(2).destination = 5
       vertexMatrix(4).connections(0).weight = 5
       vertexMatrix(4).connections(1).weight = 22
       vertexMatrix(4).connections(2).weight = 30
       
       '5 connections
       vertexMatrix(5).name = 5
       vertexMatrix(5).numConnect = 0
       vertexMatrix(5).connections(0).destination = 4
       vertexMatrix(5).connections(0).weight = 30
   
       '6 connections
       vertexMatrix(6).name = 6
       vertexMatrix(6).numConnect = 1
       vertexMatrix(6).connections(0).destination = 0
       vertexMatrix(6).connections(1).destination = 7
       vertexMatrix(6).connections(0).weight = 30
       vertexMatrix(6).connections(1).weight = 40
   
       '7 connections
       vertexMatrix(7).name = 7
       vertexMatrix(7).numConnect = 3
       vertexMatrix(7).connections(0).destination = 0
       vertexMatrix(7).connections(1).destination = 2
       vertexMatrix(7).connections(2).destination = 8
       vertexMatrix(7).connections(3).destination = 6
       vertexMatrix(7).connections(0).weight = 50
       vertexMatrix(7).connections(1).weight = 33
       vertexMatrix(7).connections(2).weight = 3
       vertexMatrix(7).connections(3).weight = 40
       
       '8 connections
      vertexMatrix(8).name = 8
      vertexMatrix(8).numConnect = 1
      vertexMatrix(8).connections(0).destination = 2
      vertexMatrix(8).connections(1).destination = 7
      vertexMatrix(8).connections(0).weight = 18
      vertexMatrix(8).connections(1).weight = 3
   
       '9 connections
      vertexMatrix(9).name = 9
      vertexMatrix(9).numConnect = 1
      vertexMatrix(9).connections(0).destination = 1
      vertexMatrix(9).connections(1).destination = 2
      vertexMatrix(9).connections(0).weight = 40
      vertexMatrix(9).connections(1).weight = 60
   End Sub

</vb>