PHPackages                             letournel/path-finder - PHPackages - PHPackages  [Skip to content](#main-content)[PHPackages](/)[Directory](/)[Categories](/categories)[Trending](/trending)[Leaderboard](/leaderboard)[Changelog](/changelog)[Analyze](/analyze)[Collections](/collections)[Log in](/login)[Sign up](/register)

1. [Directory](/)
2. /
3. [Utility & Helpers](/categories/utility)
4. /
5. letournel/path-finder

ActiveLibrary[Utility & Helpers](/categories/utility)

letournel/path-finder
=====================

Path finder algorithm

1.2.1(8y ago)142.0k2[2 issues](https://github.com/letournel/path-finder/issues)MITPHPPHP >=5.3.0

Since May 30Pushed 5y ago3 watchersCompare

[ Source](https://github.com/letournel/path-finder)[ Packagist](https://packagist.org/packages/letournel/path-finder)[ RSS](/packages/letournel-path-finder/feed)WikiDiscussions master Synced 1mo ago

READMEChangelog (4)Dependencies (1)Versions (6)Used By (0)

PathFinder - The best route is the shortest
===========================================

[](#pathfinder---the-best-route-is-the-shortest)

[![Latest Stable Version](https://camo.githubusercontent.com/87a902187bc2936a963718ee10f1e42f63f1846a46280d347e578054ba804834/68747470733a2f2f706f7365722e707567782e6f72672f6c65746f75726e656c2f706174682d66696e6465722f762f737461626c652e706e67)](https://packagist.org/packages/letournel/path-finder)[![Build Status](https://camo.githubusercontent.com/56483e2eca4c354bd3f487d60d24457afdfb476422950ba27f8762c7e887a5e2/68747470733a2f2f7472617669732d63692e6f72672f6c65746f75726e656c2f706174682d66696e6465722e7376673f6272616e63683d6d6173746572)](https://travis-ci.org/letournel/path-finder)[![Scrutinizer Code Quality](https://camo.githubusercontent.com/bd79406cda168bb33166cc9b8b674f97f4abe752978a39971b9cf97d60a206a7/68747470733a2f2f7363727574696e697a65722d63692e636f6d2f672f6c65746f75726e656c2f706174682d66696e6465722f6261646765732f7175616c6974792d73636f72652e706e673f623d6d6173746572)](https://scrutinizer-ci.com/g/letournel/path-finder/?branch=master)

PathFinder is a standalone library aiming to implement famous path and route finding algorithms in PHP to solve classical problems such as:

- **[SSP: Shortest path problem](http://en.wikipedia.org/wiki/Shortest_path_problem)**
- **[TSP: Travelling salesman problem](http://en.wikipedia.org/wiki/Travelling_salesman_problem)**

Features
--------

[](#features)

- Distances: [Chebyshev](http://en.wikipedia.org/wiki/Chebyshev_distance), [Euclidean](http://en.wikipedia.org/wiki/Euclidean_distance), [Manhattan](http://en.wikipedia.org/wiki/Manhattan_distance), Octile, Zero
- SSP solving algorithms: [AStar](http://en.wikipedia.org/wiki/A*_search_algorithm), [Dijkstra](http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm), [FloydWarshall](http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm)
- TSP solving algorithms: [NearestNeighbour](http://en.wikipedia.org/wiki/Nearest_neighbour_algorithm), [2Opt](http://en.wikipedia.org/wiki/2-opt), [3Opt](http://en.wikipedia.org/wiki/3-opt)

Roadmap
-------

[](#roadmap)

- New SSP solving algorithms: [Kruskal](http://en.wikipedia.org/wiki/Kruskal%27s_algorithm)[MooreBellmanFord](http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm)[Prim](http://en.wikipedia.org/wiki/Prim%27s_algorithm)or others
- New TSP solving algorithms: [Christofides](http://en.wikipedia.org/wiki/Christofides_algorithm), [kOpt](http://en.wikipedia.org/wiki/k-opt), [LinKernighan](http://en.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuristic)or others
- Speed optimisations
- Open to suggestions and contributions

Classes
-------

[](#classes)

#### Core Classes

[](#core-classes)

- **Heuristic**: A distance with a floating weight.
- **Node**: A node entity used in NodeGrid, NodeGraph, NodeMap or NodePath which is basically a couple of coordinates (x, y) or indices (i,j)
- **NodeGraph**: A [graph](http://en.wikipedia.org/wiki/Graph_(mathematics)) is a set of vertices connected by edges. Here, vertices are nodes and any couple of them can be connected by an edge with a floating value. By default, the graph is symmetric so the edge from vertex A to vertex B and vice versa have the same value.
- **NodeGrid**: Simply a matrix of Nodes with coordinates (x, y) or indices (i,j) using the following pattern:

```
    .--------------> j (width) coord y
    | 1,1 1,2 1,3
    | 2,1 2,2 2,3
    | 3,1 ...
    |
    i (height) coord x

```

- **NodeMap**: A map or dictionary which maps a Node (as key) to an object (as value) which can be a Node, boolean, ...
- **NodePath**: A linked list of successive Nodes which forms a path

#### Algorithms Classes

[](#algorithms-classes)

- **ShortestDistance\\Dijkstra**: Compute shortest distance with Dijkstra algorithm
- **ShortestDistance\\FloydWarshall**: Compute shortest distance with FloydWarshall algorithm
- **ShortestPath\\AStar**: Compute shortest path with AStar algorithm
- **ShortestPath\\Dijkstra**: Compute shortest path with Dijkstra algorithm
- **TravelingSalesman\\NearestNeighbour**: Compute shortest tour with NearestNeighbour algorithm
- **TravelingSalesman\\ThreeOpt**: Improve shortest tour with ThreeOpt algorithm
- **TravelingSalesman\\TwoOpt**: Improve shortest tour with TwoOpt algorithm

#### Converters Classes

[](#converters-classes)

- **Grid\\ASCIISyntax**: Allow converting map with an ASCII syntax to NodeMap, NodePath, Node Objects back and forth

#### Distances Classes

[](#distances-classes)

- **Chebyshev**: Compute the Chebyshev distance between two nodes which is max(|dx|, |dy|)
- **Euclidean**: Compute the Euclidean distance between two nodes which is sqrt(|dx|^2 + |dy|^2)
- **Manhattan**: Compute the Manhattan distance between two nodes which is |dx| + |dy|
- **Octile** : Compute the Octile distance between two nodes which is (|dx| < |dy|) ? (sqrt(2) - 1) \* |dx| + |dy|: (sqrt(2) - 1) \* |dy| + |dx|
- **Zero** : Compute the null or zero distance between two nodes A and B which is always 0

Examples
--------

[](#examples)

ASCIISyntax for maps:

- Path: '.'
- Source: '>'
- Target: '<'
- Wall: 'X'

SSP solving:

```
    require __DIR__ . '/vendor/autoload.php';

    use Letournel\PathFinder\Algorithms;
    use Letournel\PathFinder\Converters\Grid\ASCIISyntax;
    use Letournel\PathFinder\Core;
    use Letournel\PathFinder\Distances;

    function solve($map, $algorithm)
    {
        $converter = new ASCIISyntax();
        $grid = $converter->convertToGrid($map);
        $matrix = $converter->convertToMatrix($map);
        $source = $converter->findAndCreateNode($matrix, ASCIISyntax::IN);
        $target = $converter->findAndCreateNode($matrix, ASCIISyntax::OUT);

        $algorithm->setGrid($grid);
        $starttime = microtime(true);
        $path = $algorithm->computePath($source, $target);
        $endtime = microtime(true);

        if($path instanceof Core\NodePath)
        {
            echo "Path found in " . floor(($endtime - $starttime) * 1000) . " ms\n";
            echo $converter->convertToSyntaxWithPath($grid, $path);
        }
        else
        {
            echo "No path found\n";
        }
    }

    $map =
        '                ' . "\n" .
        '.XXXXXX XXXXXXXX' . "\n" .
        ' X   XX' . "\n" ;

    $distance = new Distances\Euclidean();
    $heuristic = new Core\Heuristic(new Distances\Euclidean(), 1);

    echo "Solving SSP with AStar:\n";
    solve($map, new Algorithms\ShortestPath\AStar($distance, $heuristic));
    echo "\n\n\n";

    echo "Solving SSP with Dijkstra:\n";
    solve($map, new Algorithms\ShortestPath\Dijkstra($distance));
    echo "\n\n\n";
```

Installation
------------

[](#installation)

Use composer:

```
{
    "require": {
        "letournel/path-finder" : "~1.0"
    }
}
```

Legal
-----

[](#legal)

Letournel/PathFinder is Copyright(c) 2015 Letournel

Code released under the MIT license

###  Health Score

32

—

LowBetter than 72% of packages

Maintenance17

Infrequent updates — may be unmaintained

Popularity24

Limited adoption so far

Community10

Small or concentrated contributor base

Maturity62

Established project with proven stability

 Bus Factor1

Top contributor holds 100% of commits — single point of failure

How is this calculated?**Maintenance (25%)** — Last commit recency, latest release date, and issue-to-star ratio. Uses a 2-year decay window.

**Popularity (30%)** — Total and monthly downloads, GitHub stars, and forks. Logarithmic scaling prevents top-heavy scores.

**Community (15%)** — Contributors, dependents, forks, watchers, and maintainers. Measures real ecosystem engagement.

**Maturity (30%)** — Project age, version count, PHP version support, and release stability.

###  Release Activity

Cadence

Every ~196 days

Total

5

Last Release

3221d ago

### Community

Maintainers

![](https://www.gravatar.com/avatar/026ca199e47bc900ce7d09a6bddc518417509032148f8948286dba2bcc36ffb7?d=identicon)[letournel](/maintainers/letournel)

---

Top Contributors

[![letournel](https://avatars.githubusercontent.com/u/10930937?v=4)](https://github.com/letournel "letournel (27 commits)")

---

Tags

algorithmastardijkstradistancegraphgraph-algorithmsgraphsnearest-neighbourspathfindersspssp-solving-algorithmstraveling-salesmanshortest pathdijkstraGraph algorithmstravelling salesmanastarfloydwarshallnearest neighbour2opt3opt

###  Code Quality

TestsPHPUnit

### Embed Badge

![Health badge](/badges/letournel-path-finder/health.svg)

```
[![Health](https://phpackages.com/badges/letournel-path-finder/health.svg)](https://phpackages.com/packages/letournel-path-finder)
```

###  Alternatives

[graphp/algorithms

Common mathematical graph algorithms implemented in PHP

1402.9M14](/packages/graphp-algorithms)[fisharebest/algorithm

Implementation of standard algorithms in PHP.

7192.7k1](/packages/fisharebest-algorithm)[bmichotte/dijkstra

php 7+ implementation of the Dijkstra algorithm

131.5k](/packages/bmichotte-dijkstra)[atrapalo/urlcrypt

PHP library to securely encode and decode short pieces of arbitrary binary data in URLs.

1147.6k](/packages/atrapalo-urlcrypt)

PHPackages © 2026

[Directory](/)[Categories](/categories)[Trending](/trending)[Changelog](/changelog)[Analyze](/analyze)