Dijkstra PHP Implementation

A simple PHP implementation for Dijkstra's algorithm

Generated by OpenAI ChatGPT Mar 14 Version

See Wikipedia

Installation

composer require diolan12/dijkstra

Usage

Using addVertex or addEdge method

// Adding edge
$dijkstra->addEdge('D', 'B', 5)->addEdge('D', 'C', 6);
// Is equals to adding vertex
$dijkstra->addVertex('D', ['B' => 5, 'C' => 6]);

use Diolan12\Dijkstra;

$dijkstra = new \Diolan12\Dijkstra();
// or
$dijkstra = new Dijkstra();
// or
$dijkstra = Dijkstra::instance();

// Add vertices and edges
$dijkstra->addVertex('A', ['B' => 3, 'C' => 2]);
$dijkstra->addVertex('B', ['A' => 3, 'C' => 1, 'D' => 5]);
$dijkstra->addVertex('C', ['A' => 2, 'B' => 1, 'D' => 6]);
$dijkstra->addEdge('D', 'B', 5, true)->addEdge('D', 'C', 6, true);

$paths = $dijkstra->findShortestPath('A', 'D'); // [A, C, D]

Using graph via class instantiation

Creating graph like this

$graph = [
    'A' => [
        'B' => 3,
        'C' => 2
    ],
    'B' => [
        'A' => 3,
        'C' => 1,
        'D' => 5
    ],
    'C' => [
        'A' => 2,
        'B' => 1,
        'D' => 6
    ],
    'D' => [
        'B' => calcDist(1, 3, 1, 6),
        'C' => 6
    ]
];

$dijkstra = Dijkstra::instance($graph);

Is the same with this method

$dijkstra->addVertex('A', ['B' => 3, 'C' => 2]);
$dijkstra->addVertex('B', ['A' => 3, 'C' => 1, 'D' => 5]);
$dijkstra->addVertex('C', ['A' => 2, 'B' => 1, 'D' => 6]);
$dijkstra->addEdge('D', 'B', 5)->addEdge('D', 'C', 6);

Method addVertex vs addEdge

addVertex: This method is used to add a vertex to the graph. A vertex represents a point or node in the graph. In the context of the Dijkstra algorithm, a vertex can be thought of as a location or node in a network. The addVertex method takes two parameters: the name of the vertex and an array of neighboring vertices (edges) with their corresponding edge weights. It adds the vertex and its associated edges to the graph.

addEdge: This method is used to add an edge between two vertices in the graph. An edge represents a connection or link between two vertices. In the context of the Dijkstra algorithm, an edge represents a cable route or path between two locations in a network. The addEdge method takes three parameters: the source vertex, the destination vertex, and the weight or cost of the edge. It establishes the connection between the source and destination vertices with the specified weight.

To summarize, addVertex is used to add a vertex with its neighboring edges to the graph, while addEdge is used to establish a connection (edge) between two vertices with a specified weight. Together, these methods allow you to build the graph representation required for the Dijkstra algorithm to find the shortest path between vertices in the network.

Dev Test

./vendor/bin/phpunit tests