数据科学家需要知道的5种图算法( 二 ) _图算法

2. 最短路径

文章插图

继续上面的例子，我们得到了一个德国城市的图以及它们之间的距离。
你想知道如何从法兰克福(起始节点)到慕尼黑的最短距离。
我们用来解决这个问题的算法叫做Dijkstra 。用Dijkstra自己的话来说：

从鹿特丹到[格罗宁根的最短路线是什么？一般来说，最短路径的算法是这样的，我花了大约20分钟来设计它。一天早上我在阿姆斯特丹和我的年轻的未婚妻购物，累了，我们坐在咖啡馆露台喝一杯咖啡，我就在想我能不能想出这个最短路径算法，然后我就想出来了。正如我所说，这是一个20分钟的发明。事实上，它是在1959年出版的。三年后，还可以读到，事实上，它相当不错。它如此漂亮的原因之一是我不用铅笔和纸来设计它。后来我了解到，不用铅笔和纸设计的好处之一是，你几乎不得不避免所有可以避免的复杂性。最终，令我大为惊讶的是，这个算法成了我成名的基石之一。
- Edsger Dijkstra，在对Philip L. Frana的采访中

应用

Dijkstra算法的变体广泛应用于谷歌地图中，用于寻找最短路径。
你在沃尔玛，你有不同的通道和所有通道之间的距离。你想要提供从A通道到D通道到客户的最短路径。

文章插图

你可以看到LinkedIn如何显示1级和2级的连接。幕后发生了什么？

文章插图

代码
print(nx.shortest_path(g, 'Stuttgart','Frankfurt',weight='weight')) print(nx.shortest_path_length(g, 'Stuttgart','Frankfurt',weight='weight')) -------------------------------------------------------- ['Stuttgart', 'Numberg', 'Wurzburg', 'Frankfurt'] 503你也可以找到所有的地点对之间的最短路径：
for x in nx.all_pairs_dijkstra_path(g,weight='weight'): print(x) -------------------------------------------------------- ('Mannheim', {'Mannheim': ['Mannheim'], 'Frankfurt': ['Mannheim', 'Frankfurt'], 'Karlsruhe': ['Mannheim', 'Karlsruhe'], 'Augsburg': ['Mannheim', 'Karlsruhe', 'Augsburg'], 'Kassel': ['Mannheim', 'Frankfurt', 'Kassel'], 'Wurzburg': ['Mannheim', 'Frankfurt', 'Wurzburg'], 'Munchen': ['Mannheim', 'Karlsruhe', 'Augsburg', 'Munchen'], 'Erfurt': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Erfurt'], 'Numberg': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Numberg'], 'Stuttgart': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Numberg', 'Stuttgart']}) ('Frankfurt', {'Frankfurt': ['Frankfurt'], 'Mannheim': ['Frankfurt', 'Mannheim'], 'Kassel': ['Frankfurt', 'Kassel'], 'Wurzburg': ['Frankfurt', 'Wurzburg'], 'Karlsruhe': ['Frankfurt', 'Mannheim', 'Karlsruhe'], 'Augsburg': ['Frankfurt', 'Mannheim', 'Karlsruhe', 'Augsburg'], 'Munchen': ['Frankfurt', 'Wurzburg', 'Numberg', 'Munchen'], 'Erfurt': ['Frankfurt', 'Wurzburg', 'Erfurt'], 'Numberg': ['Frankfurt', 'Wurzburg', 'Numberg'], 'Stuttgart': ['Frankfurt', 'Wurzburg', 'Numberg', 'Stuttgart']}) ....3. 最小生成树