给定起始节点和结束节点的覆盖图中所有节点的最短路径
我试图解决一个问题，其中有一个带正加权边的无向图，我需要找到一个最短的路径，该路径正好覆盖所有节点，一旦给定了起始节点和结束节点。此外，图是完整的（每个节点都连接到图中的所有其他节点）。我已经试着寻找一个算法可以解决这个问题，但我还没有找到一个解决这个问题。由于起止节点的限制，这并不完全是旅游销售员的问题。我将感谢任何帮助。
共有1个答案
如果从节点S开始，以T结束，请仅向S和T添加具有零权重边的虚拟节点D。在此图上找到一个最优的travelling salesman旅游，然后从旅游中删除虚拟节点以获得您的路径。
如果希望保留图的完备性属性，可以通过向S和T添加零权重边的虚拟节点，并向所有其他节点添加权重大于图中N最重边的权重之和的边来实现上述操作。出于实际目的，这意味着将它们的权重设置为integer.max或类似的。
-
下图是我整个图的子图。我有三种不同类型的节点，绿色、蓝色和紫色。 绿色和紫色通过蓝色节点间接连接。 蓝色节点通过加权的有向边彼此连接。蓝色边缘被加权，但绿色或紫色边缘不被加权。 我想解决的问题是：我想找到最适合绿色节点的紫色节点。，e、 g.我想说，对于绿色节点GA，三个最合适的紫色节点是V1、V4和V42。 什么使一个节点合适？ 完美的匹配应该是当绿色节点连接到紫色节点所连接的所有蓝色节点时。然
-
我有一个场景 我想从一个特定的节点（比如ID:7）开始运行BFS 如果有无法从该节点访问的节点，我想重新启动BFS（使用任何剩余节点），直到访问图的所有顶点 到目前为止，我得到的是从节点0开始并用另一个未访问的顶点重新启动的代码（部分）： 如何有效地更改此代码以满足我的要求？
-
本文向大家介绍访问C ++中所有节点的最短路径，包括了访问C ++中所有节点的最短路径的使用技巧和注意事项，需要的朋友参考一下 假设我们有一个带有N个节点的无向连通图，这些节点被标记为0、1、2，...，N-1。图的长度将为N，并且仅当节点i和j连接时，j才与列表graph [i]中的i不完全相同。我们必须找到访问每个节点的最短路径的长度。我们可以在任何节点处开始和停止，可以多次访问节点，并且可以
-
我有一个加权和无向图，有顶点。其中两个顶点是和。 我需要找到最短的路径，从开始，在结束，并通过G的所有顶点（以任何顺序）。 如何做到这一点？ 这不是旅行推销员问题：我不需要访问每个顶点一次，也不想回到第一个顶点。
-
我使用Neo4j（版本3.4.1）和Spring-data-neo4j（5.0.10）。RELEASE）在我的应用程序中。我也在使用OGM。 我的节点之间有以下关系： 车辆（V）具有部件（P1和P2）。零件可从经销商处购买（D1、D2和D3）。零件本身可以相互链接（例如P2与P1链接） 我正在尝试编写一个密码查询，以获取与id匹配的零件节点。我希望获取该节点及其相关节点和关系。 下面是我的查询：
-
我在leetcode中遇到了一个名为“二叉树相机”的问题。 我在想如何处理这个类似的问题：- 你必须把摄像机放在一个图的节点上，这样整个图就被覆盖了。一个节点上的摄像机监视它的所有近邻节点和它自己。找到覆盖所有节点所需的最小摄像机数量。