代码之家 › 专栏 › 技术社区 › Schilcote

在两个顶点之间创建成本最低的路径

graph-algorithm graph-theory algorithm

Schilcote · 技术社区 · 8 年前

我有一个加权无向图。如果图中的两个顶点之间没有路径,我想在它们之间创建一条路径,方法是在图中添加边,尽可能少地增加图的总权重。是否有已知的算法来确定要添加哪些边?

一个类似的问题是,如果我有一个国家的道路系统的图表,其中有两个城市无法通过道路彼此连接,我想建立最短的一组新道路,将它们连接起来。它们之间可能还有其他城市两者都不相连,如果它们存在,我想利用它们。

下面是一个小例子;红色和绿色是我想要连接的顶点,黑色的线是现有的边,蓝色的线代表我想要存在的路径。

是否有已知的算法给出了该路径中丢失的边?

一个类似的问题是,如果我有一个国家的道路系统的图表,其中有两个城市无法通过道路彼此连接,我想建立最短的一组新道路,将它们连接起来。它们之间可能还有其他城市两者都没有联系,如果它们存在,我想利用它们。

下面是一个小例子;红色和绿色是我想要连接的顶点,黑色的线是现有的边,蓝色的线代表我想要存在的路径。

是否有已知的算法给出了该路径中丢失的边?

3 回复 | 直到 8 年前

Dave 8 年前

libik 8 年前

Eric Yang 8 年前

推荐文章

Bala Ji · 以下BFS的实施效率如何?

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

NeoExceptCodeBad · 如果我有很多垂直线,我如何找到它们的边缘?

2 年前

VIAGC · 使用相邻列表创建图形

2 年前

Alexander · 提取节点属性最大值的键

3 年前

R3FL3CT · 如何在Python中将一组网站及其链接转换为有向图?

3 年前

Szyszka947 · 我什么时候可以假设Dijkstra算法中的某个顶点已经完成了最短路径

3 年前

amonroejj · 实现基于节点的工作流的一般原则,如Unreal、Blender、Alteryx等?

8 年前

quantummidget · 正在查找BFS父关系数组

8 年前