README

简单 PHP 实现 Dijkstra 算法

由 OpenAI ChatGPT 生成 3月14日版本

参见 维基百科

安装

composer require diolan12/dijkstra

使用

使用 addVertex 或 addEdge 方法

// 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]

通过类实例化使用图

创建图形如下

$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);

与这种方法相同

$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);

方法 addVertex 与 addEdge

addVertex: 此方法用于向图中添加顶点。顶点表示图中的一个点或节点。在 Dijkstra 算法的上下文中，顶点可以被视为网络中的位置或节点。addVertex 方法接受两个参数：顶点名称和与相邻顶点（边）对应的边权重数组。它将顶点和其相关边添加到图中。

addEdge: 此方法用于在图中添加两个顶点之间的边。边表示两个顶点之间的连接或链接。在 Dijkstra 算法的上下文中，边表示网络中两个位置之间的电缆路线或路径。addEdge 方法接受三个参数：源顶点、目标顶点和边的权重或成本。它使用指定的权重在源顶点和目标顶点之间建立连接。

总结一下，addVertex 用于向图中添加带有其相邻边的顶点，而 addEdge 用于在两个顶点之间建立带有指定权重的连接（边）。这两个方法共同允许您构建 Dijkstra 算法在网络上找到顶点之间最短路径所需的图表示。

开发测试

./vendor/bin/phpunit tests