igraph - 在有向未加权图中找到 N 个集合之间的最短路径

Question

我想为以下问题找到一种算法：给定一个有向图 G，其起点为 s 和 N 组节点，我需要找到一条从起始节点开始的路径，然后到达每个集合中的至少一个节点。并非所有节点都在集合中——只有其中一些。没有多于一组的节点。

例如：

1. 起点：[n1]
2. 第一组：[n5,n6,n8,n9]
3. 第二组：[n2,n10]
4. 第三组：[n4,n7]
5. 第四组：[n3]
6. 其他节点：[m1..m7]

显示图形边缘：

在这种情况下，最短路径将是：

• [n1,m3,m4,m5,n3,m6,n2,m7,n9]
• [n1,m1,n7,m5,n3,m6,n2,m7,n9]

这个问题类似于旅行推销员问题（维基百科）的概括，但在这种情况下，图是有方向的且未加权的。此外，我们有一个已知的起点，我们不仅有集合中的节点，而且我们可以多次在同一个节点上行走。

我尝试从一种惰性快速方法开始，使用 Dijkstra 从开始到所有集合中的所有节点搜索最近的节点，然后从计算中删除该集合并继续从该集合中搜索下一个最近的节点观点。

很容易注意到这种方式并没有给出最短路径，但真正的问题是有时它会陷入死胡同，即使有路径也会返回“无路径”。

我可以看到可以使用的一种天真的方法是创建一个函数来计算集合的每个特定排列，并使用类似于此处建议的算法来解决一个接近但更简单的问题。

它将花费 O(|N|! * 2^(所有 N 个集合中所有节点的数量))

添加惰性方式的代码（对不起，混乱）。

    from Queue import Queue
    from my_utils import RGBtoHex
    from igraph import *
    from random import choice
    
    
    class path_info:
        def __init__(self, way, length_of_way, satisfied_goal):
            self.way = way
            self.length_of_way = length_of_way
            self.satisfied_goal = satisfied_goal
    
    
    class graph_actions():
        # Goal point has a "start" node and all other goal points are saved in a dictionary
        def __init__(self, graph, goal_points):
            self.graph = graph
            self.goal_points = goal_points
            self.best_path = list()
    
        def calculate_best_path(self):
            self.best_path = list()
            queued_best_path = scatter(self.graph, self.goal_points)
    
            while not queued_best_path.empty():
                self.best_path.append(queued_best_path.get())
    
            return self.best_path
    
    
    def scatter(graph, goal_points):
        best_path = Queue()
        starting_point = goal_points["start"]
        del goal_points["start"]
    
        paths_dict = dict()
        return find_best_way(best_path, goal_points, graph, paths_dict, starting_point)
    
    
    def find_best_way(best_path, goal_points, graph, paths_dict, starting_point):
        last = -1
        while len(goal_points) > 0:
            vertex_color = known_colors[choice(known_colors.keys())]
            for vertex in goal_points.keys():
                # Find shortest paths from vertex
                # Color vertex
                graph.vs.find(str(vertex).encode('ascii', 'replace'))["Fill Color"] = RGBtoHex(vertex_color)
                # Find shortest path if exist with igraph function
                way = graph.get_shortest_paths(starting_point, vertex)
                if len(way[0]) != 0:
                    if (last != -1):
                        # Taking out the first node that is the end of the last route taken
                        way[0].pop(0)
                    paths_dict[vertex] = path_info(way, len(way[0]), goal_points[vertex])
    
            # Find the closest node
            stage = min(paths_dict, key=lambda x: paths_dict[x].length_of_way)
    
            # Transfer from list to queue
            for step in paths_dict[stage].way[0]:
                best_path.put(step)
                last = step
    
            # Delete the other nodes with of the same group from the goal list
            for key, value in goal_points.items():
                if paths_dict.has_key(stage) and value == paths_dict[stage].satisfied_goal:
                    del goal_points[key]
                    if key != stage:
                        del paths_dict[key]
            del paths_dict[stage]
    
            # Saving the last node of this route
            starting_point = last
        graph.save("states_graph_color.graphml", "graphml")
        return best_path

有没有比天真的更好的方法？如果没有，我可以使用启发式方法来做到这一点吗？我还想知道 igraph 是否以更干净的方式解决了这个问题。

即使只有天真的方式是可能的，我也不确定如何实现它。

标签： igraphshortest-path