PHPackages g105b/graph - 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. [Search & Filtering](/categories/search) 4. / 5. g105b/graph ActiveLibrary[Search & Filtering](/categories/search) g105b/graph =========== Implementation of Dijkstra's algorithm v1.0.1(3y ago)09[2 PRs](https://github.com/g105b/graph/pulls)PHPPHP >=8.1 Since Dec 29Pushed 3y ago1 watchersCompare [ Source](https://github.com/g105b/graph)[ Packagist](https://packagist.org/packages/g105b/graph)[ GitHub Sponsors](https://github.com/sponsors/g105b)[ RSS](/packages/g105b-graph/feed)WikiDiscussions master Synced 1mo ago READMEChangelog (4)Dependencies (2)Versions (7)Used By (0) Implementation of Dijkstra's algorithm ====================================== [](#implementation-of-dijkstras-algorithm) Finds the shortest path between two nodes in a graph, featuring asymmetric, weighted connections. [See the Wikipedia article on Dijkstra's algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm), and see the example provided on the Wikipedia article in `example/wikipedia.php`. This repository represents a `Graph` object, which can contain multiple `Node` objects. Nodes can be given multiple `Connection` objects, which connect two Nodes -- in one direction -- with a weight. A bidirectional connection requires two separate connections, and a bidirectional connection may have different weights in either direction. Given a starting `Node` and an ending `Node`, the algorithm provides an array of `Node` objects that represent the shortest path between the `Connection`s in the `Graph`. The underlying data structure in this implementation is a [Priority Queue](https://www.php.net/manual/en/class.splpriorityqueue.php). Example usages -------------- [](#example-usages) - In a city, many roads are connected with junctions. Some roads are faster than others. With a list of all junctions as Nodes, and all roads as Connections, from point A to point B (any two junctions) in the city, what is the path that takes the least amount of travel time, given that longer roads may have faster speeds? This is sometimes known as "[The Travelling Salesperson problem](https://en.wikipedia.org/wiki/Travelling_salesperson_problem)". - In computer networks, multiple devices are connected with physical wire or wireless radio links. Each link has its own bandwidth. When transferring data between device A and device B, calculations can be made to optimise speed of transfer versus cost of bandwidth. - In a national electrical grid simulation, there will be hundreds of parallel routes, all with different lengths and number of connected homes/businesses. The flow of electricity will always flow through the path of least resistance, and calculating this path for the simulation will allow for better efficiencies in the grid. - A large social network of a billion users may need to provide context to connections outside your personal network - suggesting that you might know person A because you are connected to person B, who is connected to person C, who in turn, is connected to person A. Complexity & efficiency --------------------------- [](#complexity--efficiency) In this implementation, all nodes of the graph are imported into the Priority Queue. This is not required for the shortest path to be calculated, but is done this way for completeness and code readability. From testing, the underlying optimisations of the SplPriorityQueue provide their own optimisations, and no noticeable efficiency difference can be perceived when only adding the nodes as they are detected. Below is the result of a stress test, available at `example/complexity.php`, sorted by seconds taken to execute. The test was performed on a 2017 model ThinkPad X1 Carbon laptop, generation 6 (Intel Core vPro i7-8650U). Each row of the table represents a separate Graph, showing the total nodes in the first column and number of connections in the second column. Complexity is calculated by multiplying Nodes by Connections. The `Graph::findShortestPath()` function takes an optional callback function. If provided, it is called for each connection of each discovered node. This is counted and labelled "Iterations". Seconds is calculated for the `findShortestPath` call, not including any setup time. The Complexity:Seconds relationship is exponential, and begins rising past 1 second after 10,000 Nodes with 5,000 connections. NodesConnectionsComplexityIterationsSeconds100000.0001011010.0001055020.000101010060.000100110000.000100101,00030.000100505,000320.00010010010,000280.0001,0001010,00060.0001,000100100,000950.00810,0001001,000,000200.0181,000500500,0004380.0351,0001,0001,000,0009060.06210,00010,000100,000,0009280.64110,0001,00010,000,0009960.70010,0005,00050,000,0004,9103.373100,0001,000100,000,0008305.630100,00010,0001,000,000,0006,38845.002100,00050,0005,000,000,00025,515228.543100,000100,00010,000,000,00070,283992.409Future optimisations -------------------- [](#future-optimisations) The repository is currently written as a pure implementation of the algorithm, but many future optimisations are possible. TThis can be achieved by extending the base classes provided in this repository. Optimisations are often incredibly specific to particular use cases. A typical optimisation with this algorithm is to introduce caching, and an amount of estimation (a close-enough shortest path). This can be achieved by choosing how many steps to cache for each node (X), then storing a list of all connections within X steps. This information can be stored within the Graph, greatly reducing the time complexity required to calculate lengthy paths in enormous Graphs, with the trade-off of being an estimation, rather than a perfect calculation. Another optimisation is to split the loop into multiple index-based chunks, so each chunk can be run in parallel on separate threads, or even separate computers. ### Health Score 25 — LowBetter than 37% of packages Maintenance20 Infrequent updates — may be unmaintained Popularity4 Limited adoption so far Community4 Small or concentrated contributor base Maturity59 Maturing project, gaining track record 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 ~4 days Total 4 Last Release 1224d ago Major Versions v0.0.2 → v1.0.02022-12-30 ### Community Maintainers ![](https://www.gravatar.com/avatar/9e42344b91ce4b91ab57875969f67a0a6a48de570a08bc65d673b06b72fd3a3f?d=identicon)[g105b](/maintainers/g105b) --- Tags djikstradjikstra-algorithmgraphgraph-algorithmspriority-queuesearchsearch-algorithmshortest-pathshortest-path-algorithmtraveltravelling-salesmantravelling-salesman-problemtreetree-structure ### Code Quality TestsPHPUnit Static AnalysisPHPStan Type Coverage Yes ### Embed Badge ![Health badge](/badges/g105b-graph/health.svg) ``` [![Health](https://phpackages.com/badges/g105b-graph/health.svg)](https://phpackages.com/packages/g105b-graph) ``` ### Alternatives [ruflin/elastica Elasticsearch Client 2.3k50.4M203](/packages/ruflin-elastica)[opensearch-project/opensearch-php PHP Client for OpenSearch 15024.3M65](/packages/opensearch-project-opensearch-php)[mailerlite/laravel-elasticsearch An easy way to use the official PHP ElasticSearch client in your Laravel applications. 934529.3k2](/packages/mailerlite-laravel-elasticsearch)[massive/search-bundle Massive Search Bundle 721.4M13](/packages/massive-search-bundle)[shyim/opensearch-php-dsl OpenSearch/Elasticsearch DSL library 175.9M9](/packages/shyim-opensearch-php-dsl)[outl1ne/nova-multiselect-filter Multiselect filter for Laravel Nova. 45802.7k3](/packages/outl1ne-nova-multiselect-filter) PHPackages © 2026 [Directory](/)[Categories](/categories)[Trending](/trending)[Changelog](/changelog)[Analyze](/analyze)