Dijkstra 算法如何使其工作定向

Question

我正在使用下面的方法来实现寻找最短路径的算法。

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class DijkstraAlgorithm {

        private final List<Node> nodes;
        private final List<Edge> edges;
        private Set<Node> settledNodes;
        private Set<Node> unSettledNodes;
        private Map<Node, Node> predecessors;
        private Map<Node, Integer> distance;

        public DijkstraAlgorithm(Graph graph) {
            // create a copy of the array so that we can operate on this array
            this.nodes = new ArrayList<Node>(graph.getNodelIst());
            this.edges = new ArrayList<Edge>(graph.getEdgeList());
        }

        public void execute(Node source) {
            settledNodes = new HashSet<Node>();
            unSettledNodes = new HashSet<Node>();
            distance = new HashMap<Node, Integer>();
            predecessors = new HashMap<Node, Node>();
            distance.put(source, 0);
            unSettledNodes.add(source);
            while (unSettledNodes.size() > 0) {
                Node node = getMinimum(unSettledNodes);
                settledNodes.add(node);
                unSettledNodes.remove(node);
                findMinimalDistances(node);
            }
        }

        private void findMinimalDistances(Node node) {
            List<Node> adjacentNodes = getNeighbors(node);
            for (Node target : adjacentNodes) {
                if (getShortestDistance(target) > getShortestDistance(node)
                        + getDistance(node, target)) {
                    distance.put(target, getShortestDistance(node)
                            + getDistance(node, target));
                    predecessors.put(target, node);
                    unSettledNodes.add(target);
                }
            }

        }

        private int getDistance(Node node, Node target) {
            for (Edge edge : edges) {
                if (edge.getSourceNode().equals(node)
                        && edge.getEndNode().equals(target)) {
                    return edge.getWeight();
                }
            }
            throw new RuntimeException("Should not happen");
        }

        private List<Node> getNeighbors(Node node) {
            List<Node> neighbors = new ArrayList<Node>();
            for (Edge edge : edges) {
                if (edge.getSourceNode().equals(node)
                        && !isSettled(edge.getEndNode())) {
                    neighbors.add(edge.getEndNode());
                }
            }
            return neighbors;
        }

        private Node getMinimum(Set<Node> vertexes) {
            Node minimum = null;
            for (Node vertex : vertexes) {
                if (minimum == null) {
                    minimum = vertex;
                } else {
                    if (getShortestDistance(vertex) < getShortestDistance(minimum)) {
                        minimum = vertex;
                    }
                }
            }
            return minimum;
        }

        private boolean isSettled(Node vertex) {
            return settledNodes.contains(vertex);
        }

        private int getShortestDistance(Node destination) {
            Integer d = distance.get(destination);
            if (d == null) {
                return Integer.MAX_VALUE;
            } else {
                return d;
            }
        }

    /*
     * This method returns the path from the source to the selected target and
     * NULL if no path exists
     */
    public LinkedList<Node> getPath(Node target) {
        LinkedList<Node> path = new LinkedList<Node>();
        Node step = target;
        // check if a path exists
        if (predecessors.get(step) == null) {
            return null;
        }
        path.add(step);
        while (predecessors.get(step) != null) {
            step = predecessors.get(step);
            path.add(step);
        }
        // Put it into the correct order
        Collections.reverse(path);
        return path;
    }


    }

这很好用，但是我现在希望向边缘添加一个方向，运行使用相同的方法指向 return 一个定向的 PathList。例如，我将为双向传递 11，为 --> 传递 01，为 <--传递 10。有没有人有这方面的经验，我理解这个概念，但实际上编码上面的方法来解释方向性给我带来了问题？

有人可以帮忙吗？

Answer 1

我认为最简单的方法是保持方向边不变，如果连接是 bi-directional，则创建两条边。

转述 NodeAID、NodeBID、01 给出 edges.add(new Edge(NodeAID, NodeBID))

NodeAID, NodeBID, 10 给出 edges.add(new Edge(NodeBID, NodeAID))

和 NodeAID、NodeBID、11 给出

edges.add(new Edge(NodeAID, NodeBID));    
edges.add(new Edge(NodeBID, NodeAID));

您可以创建一个同时处理单向和双向的边缘接口，但我认为这会使它变得更加复杂，因为边缘开始在不同的方向上具有不同的信念。

Dijkstra 算法如何使其工作定向

Dijkstra Algorithm how to make it work directed

java

android

graph-theory

dijkstra