Clone wiki

dijkstra-shortest-path / Home

Dijkstra's shortest path algorithm

This is a simple implementation of Dijkstra's shortest path algorithm in PHP.

Overview | Screenshots | Sandbox

Features

The implementation contains only two classes:

  • a generic graph class that lets you to build a generic weighted/non-weighted directed/undirected graph by adding the nodes and the edges between them
  • a class for computing the shortest path between two nodes by using Dijkstra's algorithm

Examples

There are available several usage exapmples for these classes :

  • an examples that parses your PHP project files and shows you which files are the most dependent/independent in their directed unweighted graph (see also this)
  • an basic example for computing the shortest path between some arbitray nodes A,B,...H in a directed weighted graph
  • an example that uses a list of cities as nodes in a directed weighted graph and finds the shortest route between any two of them
  • an example like the one above except that the graph is undirected weighted
  • an interactive example like the one above that uses the Google Map API for showing interactively the route in the Google's Map

Dependencies

There are no dependency whatsoever.

Usage

Just download and run them at your console/terminal.
Note that the last example (the interactive one) requires to be installed on a webserver (it's a web-browser interactive demo).

Updated