迪杰斯特拉算法如何使其在有向图中运作

huangapple go评论68阅读模式
英文:

Dijkstra Algorithm how to make it work directed

问题

以下是你要求的代码部分的中文翻译:

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) {
        // 创建数组的副本以便进行操作
        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("不应该发生的情况");
    }

    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> vertices) {
        Node minimum = null;
        for (Node vertex : vertices) {
            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;
        }
    }

    /*
     * 此方法返回从源节点到选择的目标节点的路径,如果没有路径则返回 NULL
     */
    public LinkedList<Node> getPath(Node target) {
        LinkedList<Node> path = new LinkedList<Node>();
        Node step = target;
        // 检查是否存在路径
        if (predecessors.get(step) == null) {
            return null;
        }
        path.add(step);
        while (predecessors.get(step) != null) {
            step = predecessors.get(step);
            path.add(step);
        }
        // 将路径按正确顺序排列
        Collections.reverse(path);
        return path;
    }
}

关于你的问题,你现在希望为边添加一个方向,并使用相同的方法运行有向版本,以返回一个有向路径列表。你可以使用例如 "11" 表示双向,"01" 表示 -->,"10" 表示 <--。你想要根据方向性修改上述方法,但在实际编码中遇到了问题。有人能帮助你吗?

英文:

I am using the method below to implement the algorithm to find the shortest path.

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&lt;Node&gt; nodes;
private final List&lt;Edge&gt; edges;
private Set&lt;Node&gt; settledNodes;
private Set&lt;Node&gt; unSettledNodes;
private Map&lt;Node, Node&gt; predecessors;
private Map&lt;Node, Integer&gt; distance;
public DijkstraAlgorithm(Graph graph) {
// create a copy of the array so that we can operate on this array
this.nodes = new ArrayList&lt;Node&gt;(graph.getNodelIst());
this.edges = new ArrayList&lt;Edge&gt;(graph.getEdgeList());
}
public void execute(Node source) {
settledNodes = new HashSet&lt;Node&gt;();
unSettledNodes = new HashSet&lt;Node&gt;();
distance = new HashMap&lt;Node, Integer&gt;();
predecessors = new HashMap&lt;Node, Node&gt;();
distance.put(source, 0);
unSettledNodes.add(source);
while (unSettledNodes.size() &gt; 0) {
Node node = getMinimum(unSettledNodes);
settledNodes.add(node);
unSettledNodes.remove(node);
findMinimalDistances(node);
}
}
private void findMinimalDistances(Node node) {
List&lt;Node&gt; adjacentNodes = getNeighbors(node);
for (Node target : adjacentNodes) {
if (getShortestDistance(target) &gt; 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)
&amp;&amp; edge.getEndNode().equals(target)) {
return edge.getWeight();
}
}
throw new RuntimeException(&quot;Should not happen&quot;);
}
private List&lt;Node&gt; getNeighbors(Node node) {
List&lt;Node&gt; neighbors = new ArrayList&lt;Node&gt;();
for (Edge edge : edges) {
if (edge.getSourceNode().equals(node)
&amp;&amp; !isSettled(edge.getEndNode())) {
neighbors.add(edge.getEndNode());
}
}
return neighbors;
}
private Node getMinimum(Set&lt;Node&gt; vertexes) {
Node minimum = null;
for (Node vertex : vertexes) {
if (minimum == null) {
minimum = vertex;
} else {
if (getShortestDistance(vertex) &lt; 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&lt;Node&gt; getPath(Node target) {
LinkedList&lt;Node&gt; path = new LinkedList&lt;Node&gt;();
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;
}
}

This works fine, however i now wish to add a direction to my edges and run the same method directed, to return a directed PathList. i will pass a 11 for bidirectional, 01 for --> and 10 for <-- just for example. Does anyone have experience of this, i understand the concept but actually coding the method above to account for directionality is causing me an issue?

Can anyone help with this?

答案1

得分: 1

我认为最简单的方法是保持您的方向边如旧,并在连接是双向的情况下创建两条边。

重新表述的内容:
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));

您可以创建一个处理单向和双向的 Edge 接口,但我认为这会在边开始在不同方向上具有不同联系时使其变得更加复杂。

英文:

I think the easiest is to keep your directional edges as is and create two edges if the connection is bi-directional.

Paraphrased
NodeAID, NodeBID, 01 gives edges.add(new Edge(NodeAID, NodeBID))

NodeAID, NodeBID, 10 gives edges.add(new Edge(NodeBID, NodeAID))

and NodeAID, NodeBID, 11 gives

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

You could create an Edge interface which handles both unidirectional and bidirectional, but I think that would make it more complex one the edges start having different faiths in the different directions.

huangapple
  • 本文由 发表于 2020年9月8日 16:12:28
  • 转载请务必保留本文链接:https://go.coder-hub.com/63789782.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定