Shortest Distance Algorithm with PHP - Dijkstra’s Shortest Path Algorithm

shortestDistance.php

<?php
/**
 * Created by PhpStorm.
 * User: adriano
 * Date: 08/11/19
 * Time: 14:30
 */

class Edge {

	private $vertex;
	private $distance;

	public function __construct( Vertex $vertex, int $distance ) {
		$this->vertex   = $vertex;
		$this->distance = $distance;
	}

	public function getVertex(): Vertex {
		return $this->vertex;
	}

	public function getDistance(): int {
		return $this->distance;
	}
}

class Vertex {

	private $data;
	private $edges = [];

	public function __construct( $data ) {
		$this->data = $data;
	}

	public function getData() {
		return $this->data;
	}

	public function getEdges(): array {
		return $this->edges;
	}

	public function setEdges( array $edges ): void {
		$this->edges = $edges;
	}
}

$a = new Vertex( 'A' );
$b = new Vertex( 'B' );
$c = new Vertex( 'C' );
$d = new Vertex( 'D' );
$e = new Vertex( 'E' );
$f = new Vertex( 'F' );

$a->setEdges( [
	              new Edge( $b, 6 ),
	              new Edge( $d, 1 ),
              ] );

$d->setEdges( [
	              new Edge( $a, 1 ),
	              new Edge( $f, 1 ),
              ] );

$e->setEdges( [
	              new Edge( $d, 1 ),
	              new Edge( $b, 2 ),
	              new Edge( $c, 5 ),
              ] );

$b->setEdges( [
	              new Edge( $a, 6 ),
	              new Edge( $d, 2 ),
	              new Edge( $e, 2 ),
	              new Edge( $c, 5 ),
              ] );

function shortestPath( $start, $end, $vertexes ) {
	$visited   = [];
	$unvisited = [];
	
	$shortestDistanceTable[ $start->getData() ] = [
		'shortestPath'   => 0,
		'previousVertex' => null,
	];

	foreach ( $vertexes as $vertex ) {
		$unvisited[ $vertex->getData() ] = $vertex;
	}

	$shortestDistanceTable = [];
	$currentVertex         = $start;

	while ( $unvisited ) {
		$closestEdge = null;

		foreach ( $currentVertex->getEdges() as $edge ) {

			if ( isset( $visited[ $edge->getVertex()->getData() ] ) ) {
				continue;
			}

			if ( ! $closestEdge ) {
				$closestEdge = $edge;
			}

			$newDistance     = $shortestDistanceTable[ $currentVertex->getData() ]['shortestPath'] + $edge->getDistance();
			$currentDistance = $shortestDistanceTable[ $edge->getVertex()->getData() ] ?? null;

			if ( $currentDistance === null || $newDistance < $currentDistance['shortestPath'] ) {
				$shortestDistanceTable[ $edge->getVertex()->getData() ] = [
					'shortestPath'   => $newDistance,
					'previousVertex' => $currentVertex,
				];
			}

			if ( $closestEdge->getDistance() > $edge->getDistance() ) {
				$closestEdge = $edge;
			}
		}

		if ( ! isset( $visited[ $currentVertex->getData() ] ) ) {
			$visited[ $currentVertex->getData() ] = $currentVertex;
			unset( $unvisited[ $currentVertex->getData() ] );
		}

		if ( ! $closestEdge ) {
			$currentVertex = $shortestDistanceTable[ $currentVertex->getData() ]['previousVertex'];
			continue;
		}

		$currentVertex = $closestEdge->getVertex();
	}

	$shortestPath = [ $end->getData() ];
	$currentPath  = $shortestDistanceTable[ $end->getData() ];

	while ( isset( $currentPath['previousVertex'] ) ) {
		$shortestPath[] = $currentPath['previousVertex']->getData();
		$currentPath    = $shortestDistanceTable[ $currentPath['previousVertex']->getData() ];
	}

	return [
		'shortestDistance' => $shortestDistanceTable[ $end->getData() ]['shortestPath'],
		'shortestPath'     => array_reverse( $shortestPath ),
	];
}

shortestPath( $a, $c, [ $a, $b, $c, $d, $e ] );