Dijkstra Algorithm how to make it work directed Code Answer

Hello Developer, Hope you guys are doing great. Today at Tutorial Guruji Official website, we are sharing the answer of Dijkstra Algorithm how to make it work directed without wasting too much if your time.

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.

We are here to answer your question about Dijkstra Algorithm how to make it work directed - If you find the proper solution, please don't forgot to share this with your team members.

Related Posts

Tutorial Guruji