新算法最短路径中的图算法
图算法提供了一种理解，建模和预测复杂动态的方法，例如资源或信息流，传染性或网络故障传播的路径以及对群体的影响和弹性。
本系列文章旨在帮助您更好地利用图分析和图算法，以便您可以更快地有效创新和开发智能解决方案。
上周，我们研究了Neo4j Graph Algorithms库，以及如何在连接的数据上使用它，以便在Neo4j中更轻松地获得新见解。
本周，我们开始探索寻路和图搜索算法。
这些算法从节点开始，扩展关系，直到到达目的地。
寻路算法会在尝试根据跳数或权重找到最便宜的路径时执行此操作，而搜索算法会找到可能不是最短的路径。
我们将从最短路径算法开始，该算法计算一对节点之间的最短加权路径。
最短路径用于查找物理位置之间的方向，例如行驶方向。
它还用于查找社交网络中人与人之间的隔离程度以及彼此之间的联系。
最短路径算法计算一对节点之间的最短（加权）路径。
在这一类别中，Dijkstra的算法是最著名的。
它是一种实时图形算法，被用作Web或移动应用程序中普通用户流程的一部分。
寻路历史悠久，被认为是经典的图形问题之一。 最早可以追溯到19世纪。
在1950年代初，它在备用路由的背景下得到了重视，也就是说，如果最短路径被阻塞，则找到第二条最短路径。
Edsger Dijkstra在1956年尝试展示新的ARMAC计算机时提出了他的算法。
他需要找到一个不熟悉计算的人能够理解的问题和解决方案，并且他设计了现在称为Dijkstra的算法。
后来，他将其实现为荷兰64个城市的交通地图略微简化。
- 查找物理位置之间的方向。
这是最常见的用法，并且诸如Google Maps之类的网络地图工具使用最短路径算法或它的一种变体来提供行车路线。 - 社交网络使用该算法查找人与人之间的隔离度。
例如，当您在LinkedIn上查看某人的个人资料时，它会在联系图中指示有多少人将您分开，并列出您的相互联系。
小费：
Dijkstra不支持负重量。
该算法假定将关系添加到路径永远不会使路径变短-负权重会违反不变式。
让我们在一个小的数据集上计算最短路径。
以下Cypher语句创建一个示例图，其中包含它们之间的位置和连接。
现在，我们可以运行最短路径算法来查找和之间的最短路径。
执行以下查询。
最快的路线将我们带到，、、和，总费用为160：
我们已经在寻路算法列表中介绍了第一个，即最短路径。
下周，我们将使用来自全球领先的图形数据库Neo4j的示例，通过“最短路径”算法继续研究寻路算法。