A laravel implementation of Dijkstra algorithm.
Dijkstra's algorithm, conceived by computer scientist Edsger Dijkstra, is a graph search algorithm that solves in single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree.
First you need to add the component to your composer.json
composer require noweh/laravel-dijkstra
Update your packages with composer update or install with composer install.
Laravel uses Package Auto-Discovery, so doesn't require you to manually add the ServiceProvider.
After updating composer, add the ServiceProvider to the providers array in config/app.php
Noweh\Dijkstra\DijkstraServiceProvider::class,
The migrations of this package are publishable under the "migrations" tag via:
php artisan vendor:publish --provider="Noweh\Dijkstra\DijkstraServiceProvider" --tag="migrations"
<?php
/** @var IPointsService $pointsService */
$pointsService = \Dijkstra::pointsService();
// Create all points
$pointsService->createStructure([
['name' => 'A', 'x' => 250, 'y' => 120],
['name' => 'B', 'x' => 120, 'y' => 228],
// ...
['name' => 'H', 'x' => 400, 'y' => 460]
], [
['A' => 'B'],
// ...
['H' => 'D']
]);
// add One point
$pointsService->addPoint(['name' => 'I', 'x' => 60, 'y' => 30]);
// Remove one point
$pointsService->removePoint('B');
// Add relation
$pointsService->addRelation(['E' => 'I']);
// Remove relation
$pointsService->removeRelation(['A' => 'B']);
// Retrieve all points
dump($pointsService->getPoints());
/** @var IGraphService $graphService */
$graphService = \Dijkstra::graphService();
$pointFrom = $pointsService->getPoint('B');
$pointTo = $pointsService->getPoint('C');
dump($graphService->findShortestPath($pointFrom, $pointTo));
// Draw a Graph
$graphService->drawGraph($pointFrom, $pointTo);