The question is published on by Tutorial Guruji team.
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<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;
}
}
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?
Answer
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.