|
假设你有沃尔玛市肆中各个过道位置和过道之间间隔的数据。您但愿为从 A 到 D 的顾主提供最短路径。
你已经看到 LinkedIn 表现一级毗连和二级毗连的方法。而这背后的机制是什么呢？
代码
- 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']})
- ....
最小天生树（Minimum Spanning Tree，MST）
此刻我们面对另一个题目。假设我们在水管铺设公司或电线公司事变。我们必要行使起码的电线/管道来毗连图中全部都市。我们怎样做到这一点？
左： 无向图； 右： 对应 MST
应用
-
最小天生树在收集计划中有直策应用，包罗计较机收集、电信收集、交通收集、供水收集和电网（最初是为它们发现的）。
-
MST 用于近似观光商题目。
-
聚类：起首构建 MST，然后行使类间间隔和类内间隔确定阈值，用于冲破 MST 中某些边。
-
图像支解：起首在图上构建 MST，个中像素是节点，像素之间的间隔基于某种相似性怀抱（颜色、强度等）
代码
- # nx.minimum_spanning_tree(g) returns a instance of type graph
- nx.draw_networkx(*nx.minimum_spanning_tree*(g))
左： 无向图； 右： 对应 MST.
Pagerank
上图为谷歌提供恒久支持的页面排序算法（page sorting algorithm）。它按照输入和输出链接的数目和质量为页面打分。
应用
（编辑：湖南网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
