计算无向加权图中一组顶点之间的最短路径

Question

我有一个至少由 15 个顶点组成的无向加权图 (G)。给定一组顶点 (G')，其中 G' ⊆ G，我需要计算给定起始顶点 (v) 遍历 G' 所需的最短路径。我卡住了！我尝试了以下方法：

for (Vertex vx : G'):
    computeShortestPath (v, vx)//using Dijkstra's algo

V和G'中的任何顶点之间生成的所有路径中的最短路径将构成初始化路径（P）。然后我删除G'中已在P中访问过的所有顶点

G'.remove (P)

递归计算 P 直到：

G'.size () == 0

虽然我的算法有时似乎效率低下！对这个问题的不同补救措施有什么建议吗？

编辑：我只需要访问 G' 中的每个节点一次。

Answer 1

如果我对你的问题的理解正确，那么它本质上就是 Travelling Salesman 问题，它已被证明是 NP-hard 问题：没有有效的解决方案来解决这个问题。您提出的任何解决方案都需要随节点数量呈指数增长的资源。有返回最可能的最短路径或迭代最短路径的有效解决方案。有一些算法可以在开始搜索之前确定是否存在路径。

Djikstra 算法用于查找通过图形的最短路径，而不是访问所有节点的最短路径。

对于少量节点，最简单的解决方案是对所有路径进行详尽搜索。这看起来像：

class PathFinder {
    Path shortestPath;
    public void findShortestPath(Path currentPath, List<Node> remainingNodes) {
        if (remainingNodes.isEmpty()) {
            if (currentPath.isShorterThan(shortestPath)) {
                shortestPath = currentPath;
            }
        } else {
            for (Node node: currentPath.possibleNextNodes(remainingNodes)) {
                remainingNodes.remove(node);
                currentPath.add(node);
                findShortestPath(currentPath, remainingNodes);
                currentPath.remove(node);
                remainingNodes.add(node);
            }
        }
    }
}

出于效率原因，此算法不会复制剩余节点的路径或列表。它将用于查找 15 个节点的图形。对于数千个节点来说不是那么多。

这需要您实施 Path 和 Node 类。这是它们的一个可能的部分实现：

public class Node {
    private class Link {
        private final Node destination;
        private final int weight;
        private Link(Node destination, int weight) {
            this.destination = destination;
            this.weight = weight;
    }

    private final List<Link> links;

    public void addLink(Node destination, int weight) {
        if (!connectsTo(destination)) {
            Link link = new Link(destination, weight);
            destination.addLink(this, weight);
        }
    }

    public boolean connectsTo(Node node) {
        return links.stream.anyMatch(link -> link.destination.equals(node));
    }

    public int weightTo(Node node) {
        return links.stream.filter(link -> link.destination.equals(node))
            .findAny().orElse(0);
    }
}

public class Path {
    private int length;
    private List<Node> nodes;

    private Node lastNode() {
        return nodes.get(nodes.size() - 1);
    }

    public List<Node> possibleNextNodes(List<Node> possibleNodes) {
        if (nodes.isEmpty());
            return possibleNodes;
        return possibleNodes.stream()
            .filter(node -> lastNode().connectsTo(node))
            .filter(node -> !nodes.contains(node))
            .collect(Collectors.toList());
    }

    public boolean isShorterThan(Path other) {
        return this.length < other.length;
    }

    public void add(Node node) {
        length += lastNode().distanceTo(node);
        nodes.add(node);
    }
}

计算无向加权图中一组顶点之间的最短路径

Calculate the shortest path between a set of vertices in an undirected weighted graph

java

graph

shortest-path