README

在图中找到两个节点之间的最短路径，具有非对称、带权连接。

查看维基百科上的Dijkstra算法文章，并在example/wikipedia.php中查看维基百科文章提供的示例。

此存储库表示一个Graph对象，它可以包含多个Node对象。节点可以分配多个Connection对象，这些对象将两个节点（单向）连接起来，并带有权重。双向连接需要两个单独的连接，并且双向连接在任一方向上可能具有不同的权重。

给定一个起始Node和一个结束Node，该算法提供了一个代表图中的Connection之间的最短路径的Node对象数组。

在此实现中，底层数据结构是一个优先队列。

示例用法

在一个城市中，许多道路通过交叉路口连接。有些道路比其他道路更快。将所有交叉路口作为节点，所有道路作为连接，从城市中的A点到B点（任意两个交叉路口），找到需要最短旅行时间的路径，假设更长的道路可能有更快的速度。这有时被称为“旅行推销员问题”。
在计算机网络中，多个设备通过物理电线或无线无线电链路连接。每个链路都有自己的带宽。在设备A和设备B之间传输数据时，可以计算出优化传输速度与带宽成本的方法。
在国家电网模拟中，将有数百条并行路线，它们具有不同的长度和连接的家庭/企业数量。电流总是通过电阻最小的路径流动，对于模拟计算这条路径将有助于提高电网的效率。
一个拥有十亿用户的庞大社交网络可能需要为其个人网络之外的联系提供上下文 - 建议你可能认识A，因为你与B连接，B又与C连接，而C反过来又与A连接。

复杂度 & 效率

在此实现中，将图中的所有节点都导入优先队列。这不是计算最短路径所必需的，但这样做是为了完整性和代码的可读性。根据测试，SplPriorityQueue的底层优化提供了自己的优化，并且当仅按检测到的节点添加时，没有明显的效率差异。

以下是在example/complexity.php中可用的压力测试结果，按执行时间排序。测试在一台2017型号的ThinkPad X1 Carbon笔记本电脑（第6代Intel Core vPro i7-8650U）上执行。表格的每一行代表一个单独的图，第一列显示节点总数，第二列显示连接数。复杂度是通过节点数乘以连接数计算的。

Graph::findShortestPath() 函数接受一个可选的回调函数。如果提供，则对每个发现节点的每个连接调用它。这被计算并标记为“迭代次数”。计算findShortestPath调用所需的时间，不包括任何设置时间。

复杂度：秒的关系是指数级的，并且在超过10,000个节点和5,000个连接后1秒开始上升。

未来优化

当前仓库是算法的纯实现，但许多未来的优化是可能的。这可以通过扩展此仓库中提供的基类来实现。

优化通常非常特定于特定用例。使用此算法的一个典型优化是引入缓存和一定程度的估计（足够接近的最短路径）。这可以通过选择每个节点缓存多少步（X）来实现，然后存储所有X步内的连接列表。这些信息可以存储在图中，大大减少计算巨大图中长时间路径所需的时间复杂度，但以牺牲精确计算为代价，而是估计。

另一种优化是将循环分割成多个基于索引的块，这样每个块都可以在单独的线程或甚至单独的计算机上并行运行。

g105b / graph

维护者

详细信息

README

示例用法

复杂度 & 效率

未来优化