Header Ads Widget

Responsive Advertisement

Dijsktra Shortest Path for directed an undirected graph

Kartik Chandra Mandal January 27, 2016



An input string (input1) representing a set of paths with weighted edges, and input2 that lists specific nodes of interest. You need to find the paths connecting these specified nodes in input2, with each segment separated by #, and if no path exists, return NC for "No Connection."

Here's a solution approach in Java that parses the input, constructs paths, and finds connections:

Solution Code

java

import java.util.*;

 

public class PathFinder {

 

    // Function to parse input1 and create a graph representation

    private static Map<Integer, List<Edge>> parseGraph(String input1) {

        Map<Integer, List<Edge>> graph = new HashMap<>();

 

        // Split segments by comma

        String[] segments = input1.split(",");

        for (String segment : segments) {

            // Split edges in each segment by '#'

            String[] edges = segment.split("#");

            for (String edge : edges) {

                // Each edge format is "start-end-weight"

                String[] parts = edge.split("-");

                int start = Integer.parseInt(parts[0]);

                int end = Integer.parseInt(parts[1]);

                int weight = Integer.parseInt(parts[2]);

 

                // Add edge to the graph

                graph.putIfAbsent(start, new ArrayList<>());

                graph.get(start).add(new Edge(end, weight));

            }

        }

        return graph;

    }

 

    // Function to find the path between start and end nodes

    private static String findPath(Map<Integer, List<Edge>> graph, int start, int end) {

        // Use BFS or DFS to find the path from start to end

        Queue<Path> queue = new LinkedList<>();

        Set<Integer> visited = new HashSet<>();

        queue.add(new Path(start, new ArrayList<>()));

 

        while (!queue.isEmpty()) {

            Path path = queue.poll();

            int current = path.node;

 

            // Avoid revisiting nodes

            if (!visited.add(current)) continue;

 

            // Check if we have reached the end node

            if (current == end) {

                // Build the path string from path.nodes

                StringBuilder pathString = new StringBuilder();

                for (Edge edge : path.edges) {

                    if (pathString.length() > 0) pathString.append("#");

                    pathString.append(edge.start).append("-").append(edge.end).append("-").append(edge.weight);

                }

                return pathString.toString();

            }

 

            // Add neighbors to the queue

            if (graph.containsKey(current)) {

                for (Edge edge : graph.get(current)) {

                    List<Edge> newEdges = new ArrayList<>(path.edges);

                    newEdges.add(edge);

                    queue.add(new Path(edge.end, newEdges));

                }

            }

        }

        return "NC";  // No connection found

    }

 

    // Main function to handle input and output the result

    public static String findPaths(String input1, String input2) {

        Map<Integer, List<Edge>> graph = parseGraph(input1);

        String[] nodes = input2.split("#");

 

        StringBuilder result = new StringBuilder("{ ");

        for (int i = 0; i < nodes.length; i++) {

            int node = Integer.parseInt(nodes[i]);

            if (i > 0) result.append(", ");

           

            if (i > 0) {

                int start = Integer.parseInt(nodes[i - 1]);

                String path = findPath(graph, start, node);

                result.append(path);

            } else {

                result.append("NC"); // Initial start node has no preceding connection

            }

        }

        result.append(" }");

        return result.toString();

    }

 

    public static void main(String[] args) {

        String input1 = "{1-2-30#2-3-25#3-4-30#4-5-45#5-6-30#6-7-15#7-8-60#8-9-40,10-11-45#11-4-60#4-12-60#12-13-45#13-14-30#14-15-35,1-3-40#3-4-25#4-16-30#16-17-15#17-18-20#18-19-30#19-20-25,21-12-30#12-17-180#17-22-45}";

        String input2 = "12#18";

        System.out.println(findPaths(input1, input2));

    }

 

    // Inner classes for Edge and Path

    static class Edge {

        int end, weight;

        int start;

 

        Edge(int end, int weight) {

            this.end = end;

            this.weight = weight;

        }

    }

 

    static class Path {

        int node;

        List<Edge> edges;

 

        Path(int node, List<Edge> edges) {

            this.node = node;

            this.edges = edges;

        }

    }

}

 

Explanation

  1. Parsing the Graph: The parseGraph method constructs a directed, weighted graph from input1. Each node points to a list of Edge objects, which hold destination nodes and weights.
  2. Finding Paths: The findPath method uses BFS to explore paths between specified nodes in input2. If a path exists, it returns a formatted string. Otherwise, it returns "NC" for "No Connection."
  3. Result Formatting: The findPaths method coordinates the processing for each node in input2, building the result in the specified format.

Example Output

For input1 and input2 as given:

java

Output: { NC,12-4-60#4-16-30#16-17-15#17-18-20, NC }

 

This code should work efficiently for small to medium-sized graphs due to its use of BFS for path finding.



Second Approach


java

package com.kartik.dj;

public class ProgramSolver {

 public static void main(String[] args) {
  String input1 = "{1-2-30#2-3-25#3-4-30#4-5-45#5-6-30#6-7-15#7-8-60#8-9-40,10-11-45#11-4-60#4-12-60#12-13-45#13-14-30#14-15-35,1-3-40#3-4-25#4-16-30#16-17-15#17-18-20#18-19-30#19-20-25,21-12-30#12-17-180#17-22-45}";
  String input2 = "12#18";
  CandidateCode dj = new CandidateCode();
  dj.quickstroute(input1, input2);
 }

}

 

 

Step 2

package com.kartik.dj;

 

/**

 * Created by Kartik Chandra Mandal on 26/01/2016.

 */

 

import java.io.IOException;

import java.util.*;

 

public class CandidateCode {

 private int size;

 private HashMap<Integer, Double> weight; // store weights for each vertex

 private HashMap<Integer, Integer> previousNode; // store previous vertex

 private PriorityQueue<Integer> pq; // store vertices that need to be visited

 private WeighedDigraph graph; // graph object

 

 CandidateCode() {

 }

 

 /**

  * @return string representation of digraph

  */

 public String getWeight(int from, int to) {

  ArrayList<WeighedDigraphEdge> currentEdges = graph.edgesOf(from);

  String out = "";

  out += from + "-";

  for (WeighedDigraphEdge edge : currentEdges) {

   if (to == edge.to())

    out += edge.to() + "-" + edge.weight() + ",";

  }

  return out;

 }

 

 public String getWeightSecond(int from, int to) {

  ArrayList<WeighedDigraphEdge> currentEdges = graph.edgesOf(from);

  String out = "";

  out += from + "-";

  for (WeighedDigraphEdge edge : currentEdges) {

   if (to == edge.to())

    out += edge.to() + "-" + edge.weight() + "#";

  }

  return out;

 }

 

 public String convertData(ArrayList<Integer> nodePath) {

  Integer[] stockArr = new Integer[nodePath.size()];

  for (int j = 0; j < nodePath.size(); j++) {

   stockArr[j] = nodePath.get(j);

  }

  StringBuffer sb = new StringBuffer();

  sb.append("{ NC,");

  for (int i = 0; i < stockArr.length; i++) {

   if (i == 0) {

    int first = stockArr[i];

    int second = stockArr[i + 1];

    sb.append(getWeight(first, second));

   } else if (i > 0 && i < stockArr.length - 1) {

    int first = stockArr[i];

    int second = stockArr[i + 1];

    if (i == stockArr.length - 2) {

     sb.append(getWeight(first, second));

    } else {

     sb.append(getWeightSecond(first, second));

    }

   }

  }

  sb.append(" NC }");

  System.out.println(sb.toString());

  return sb.toString();

 }

 

 /**

  * Instantiate algorithm providing graph

  * 

  * @param graph

  *            WeighedDigraph graph

  */

 public CandidateCode(WeighedDigraph graph) {

  this.graph = graph;

  size = graph.size();

 }

 

 /**

  * Calculate shortest path from A to B

  * 

  * @param vertexA

  *            source vertex

  * @param vertexB

  *            destination vertex

  * @return list of vertices composing shortest path between A and B

  */

 public ArrayList<Integer> shortestPath(int vertexA, int vertexB) {

  previousNode = new HashMap<Integer, Integer>();

  weight = new HashMap<Integer, Double>();

  pq = new PriorityQueue<Integer>(size, PQComparator);

 

  /* Set all distances to Infinity */

  for (int vertex : graph.vertices())

   weight.put(vertex, Double.POSITIVE_INFINITY);

 

  previousNode.put(vertexA, -1); // negative means no previous vertex

  weight.put(vertexA, 0.0); // weight to has to be 0

  pq.add(vertexA); // enqueue first vertex

 

  while (pq.size() > 0) {

   int currentNode = pq.poll();

   ArrayList<WeighedDigraphEdge> neighbors = graph

     .edgesOf(currentNode);

 

   if (neighbors == null)

    continue;

 

   for (WeighedDigraphEdge neighbor : neighbors) {

    int nextVertex = neighbor.to();

 

    double newDistance = weight.get(currentNode)

      + neighbor.weight();

    if (weight.get(nextVertex) == Double.POSITIVE_INFINITY) {

     previousNode.put(nextVertex, currentNode);

     weight.put(nextVertex, newDistance);

     pq.add(nextVertex);

    } else {

     if (weight.get(nextVertex) > newDistance) {

      previousNode.put(nextVertex, currentNode);

      weight.put(nextVertex, newDistance);

     }

    }

   }

  }

 

  /* Path from A to B will be stored here */

  ArrayList<Integer> nodePath = new ArrayList<Integer>();

 

  /*

   * We are reverse walking points to get to the beginning of the path.

   * Using temporary stack to reverse the order of node keys stored in

   * nodePath.

   */

  Stack<Integer> nodePathTemp = new Stack<Integer>();

  nodePathTemp.push(vertexB);

 

  int v = vertexB;

  while (previousNode.containsKey(v) && previousNode.get(v) >= 0 && v > 0) {

   v = previousNode.get(v);

   nodePathTemp.push(v);

  }

 

  // Put node in ArrayList in reversed order

  while (nodePathTemp.size() > 0)

   nodePath.add(nodePathTemp.pop());

  convertData(nodePath);

  return nodePath;

 }

 

 /**

  * Comparator for priority queue

  */

 public Comparator<Integer> PQComparator = new Comparator<Integer>() {

 

  public int compare(Integer a, Integer b) {

   if (weight.get(a) > weight.get(b)) {

    return 1;

   } else if (weight.get(a) < weight.get(b)) {

    return -1;

   }

   return 0;

  }

 };

 

 private static String[] dataSplit(String colData) {

  String[] cols = colData.split(Constant.constantD);

  return cols;

 }

 

 public String[] quickstroute(String first, String second) {

  WeighedDigraph graph;

 

  try {

   String[] cols = dataSplit(second);

   int source = Integer.parseInt(cols[0]);

   int destination = Integer.parseInt(cols[1]);

   graph = new WeighedDigraph(first);

   CandidateCode finder = new CandidateCode(graph);

   finder.shortestPath(source, destination);

 

  } catch (IOException e) {

   System.out.println();

  }

  return null;

 }

}

 

 

Step 3>

package com.kartik.dj;

 

public interface Constant {

 

 public final String constantA = "#|\\,";

 public final String constantB = "-";

 public final String constantC = "[#,]";

 public final String constantD = "#";

 

}

 

 

Step 4>

package com.kartik.dj;

 

/**

 * Created by Kartik Chandra Mandal on 26/01/2016.

 */

public class WeighedDigraphEdge {

    private int from, to;

    private int weight;

 

    /**

     * Construct graph edge

     * @param from

     * @param to

     * @param weight

     */

    public WeighedDigraphEdge(int from, int to, int weight) {

        this.from = from;

        this.to = to;

        this.weight = weight;

    }

 

    /**

     * @return from vertex

     */

    public int from() { return from; }

 

    /**

     * @return to vertex

     */

    public int to() { return to; }

 

    /**

     * @return weight of edge between from() and to()

     */

    public int weight() { return weight; }

}

 

 

Step 5>

package com.kartik.dj;

 

/**

 * Created by Kartik Chandra Mandal on 26/01/2016.

 */

 

import java.util.HashMap;

import java.util.ArrayList;

import java.util.HashSet;

import java.util.regex.Matcher;

import java.util.regex.Pattern;

import java.io.IOException;

 

public class WeighedDigraph {

 private HashMap<Integer, ArrayList<WeighedDigraphEdge>> adj = new HashMap(); // adjacency-list

 

 public WeighedDigraph() {

 }

 

 /**

  * 

  * @param colData

  * @return

  */

 private static String[] colmnSplit(String colData) {

  String[] cols = colData.split(Constant.constantA);

  return cols;

 }

 

 private static String[] rowSplit(String colData) {

  String[] cols = colData.split(Constant.constantB);

  return cols;

 }

 

 public WeighedDigraph(String input) throws IOException {

  String substring = input.substring(1, input.length() - 1);

  try {

   Pattern regex = Pattern.compile(Constant.constantC);

   Matcher matcher = regex.matcher(substring);

   if (matcher.find()) {

    for (String col : colmnSplit(substring)) {

     String[] row = rowSplit(col);

     int from = Integer.parseInt(row[0]);

     int to = Integer.parseInt(row[1]);

     int weight = Integer.parseInt(row[2]);

 

     addEdge(new WeighedDigraphEdge(from, to, weight));

     addEdge(new WeighedDigraphEdge(to, from, weight));// if

                  // directed

                  // comment

                  // that

                  // line

    }

   }

  } catch (Exception e) {

  }

 }

 

 /**

  * @param vertex

  * @return list of edges vertex is connected to.

  */

 public ArrayList<WeighedDigraphEdge> edgesOf(int vertex) {

  return adj.get(vertex);

 }

 

 /**

  * @return list of all edges in the graph.

  */

 public ArrayList<WeighedDigraphEdge> edges() {

  ArrayList list = new ArrayList<WeighedDigraphEdge>();

 

  for (int from : adj.keySet()) {

   ArrayList<WeighedDigraphEdge> currentEdges = adj.get(from);

   for (WeighedDigraphEdge e : currentEdges) {

    list.add(e);

   }

  }

  return list;

 }

 

 /**

  * @return iterable of all vertices in the graph.

  */

 public Iterable<Integer> vertices() {

  HashSet set = new HashSet();

  for (WeighedDigraphEdge edge : edges()) {

   set.add(edge.from());

   set.add(edge.to());

  }

 

  return set;

 }

 

 /**

  * @return size of adjacency list

  */

 public int size() {

  return adj.size();

 }

 

 /**

  * @return string representation of digraph

  */

 public String toString() {

  String out = "";

  for (int from : adj.keySet()) {

   ArrayList<WeighedDigraphEdge> currentEdges = adj.get(from);

   out += from + " -> ";

 

   if (currentEdges.size() == 0)

    out += "-,";

 

   for (WeighedDigraphEdge edge : currentEdges)

    out += edge.to() + " @ " + edge.weight() + ", ";

 

   out += "\n";

  }

 

  return out;

 }

 

 /**

  * Add new edge to the system.

  * 

  * @param newEdge

  */

 public void addEdge(WeighedDigraphEdge newEdge) {

  // create empty connection set

  if (!adj.containsKey(newEdge.from()))

   adj.put(newEdge.from(), new ArrayList<WeighedDigraphEdge>());

 

  ArrayList<WeighedDigraphEdge> currentEdges = adj.get(newEdge.from());

 

  /*

   * Check if edge already exists, if it is, replace it with new one

   * assuming it needs to be updated

   */

  boolean edgeExists = false;

  for (int i = 0; i < currentEdges.size(); i++) {

   if (currentEdges.get(i).to() == newEdge.to()) {

    currentEdges.set(i, newEdge);

    edgeExists = true;

    break;

   }

  }

 

  if (!edgeExists)

   currentEdges.add(newEdge);

 

  adj.put(newEdge.from(), currentEdges);

 }

}

 

 

The provided code implements Dijkstra's algorithm to find the shortest path between nodes in a graph. It includes multiple classes to represent the graph (WeighedDigraph), its edges (WeighedDigraphEdge), and the main algorithm (CandidateCode). Here's an explanation of each class and method:

1. ProgramSolver Class

This is the entry point of the application. It provides sample inputs (input1 for the graph data and input2 for the source and destination nodes) and invokes the quickstroute method of the CandidateCode class.

2. CandidateCode Class

This class contains the implementation of Dijkstra's algorithm and additional utility methods.

Ø  Instance Variables:

ü  size: The number of vertices in the graph.

ü  weight: A map storing the minimum distance from the source node to each vertex.

ü  previousNode: A map storing the previous node in the shortest path for each vertex.

ü  pq: A priority queue to manage the nodes to be visited.

ü  graph: The graph on which the algorithm operates.

Ø  Methods:

ü  getWeight and getWeightSecond: These methods generate formatted strings representing the weight of the edge between two nodes.

ü  convertData: Converts the list of nodes in the shortest path into a formatted string.

ü  shortestPath: Implements Dijkstra's algorithm to find the shortest path between two nodes.

ü  quickstroute: Splits the input strings, creates a graph, and finds the shortest path between the specified nodes.

3. Constant Interface

This interface contains string constants used for splitting the input data.

4. WeighedDigraphEdge Class

This class represents an edge in the graph, with fields for the source node (from), destination node (to), and the weight of the edge (weight).

5. WeighedDigraph Class

This class represents a directed weighted graph using an adjacency list.

Ø  Instance Variables:

ü  adj: A map where each key is a vertex, and the value is a list of edges originating from that vertex.

Ø  Methods:

ü  colmnSplit, rowSplit: Utility methods to split the input string into columns and rows.

ü  WeighedDigraph: Constructor that parses the input string to create the graph.

ü  edgesOf: Returns the list of edges originating from a specific vertex.

ü  edges: Returns a list of all edges in the graph.

ü  vertices: Returns an iterable of all vertices in the graph.

ü  size: Returns the number of vertices in the graph.

ü  toString: Returns a string representation of the graph.

ü  addEdge: Adds a new edge to the graph, updating existing edges if necessary.

How It Works:

  1. The ProgramSolver class invokes the quickstroute method with the given input.
  2. The quickstroute method creates a WeighedDigraph from the input string and then uses the shortestPath method to find the shortest path between the two specified nodes.
  3. The shortest path is then formatted and printed.

Example Execution:

Given the input:

Ø  Graph Data (input1): A string representing a graph with nodes connected by weighted edges.

Ø  Nodes (input2): A string representing the source and destination nodes (12 and 18).

The program constructs the graph, finds the shortest path from node 12 to node 18, and prints the path and associated weights.

This implementation is useful for solving problems related to finding the shortest paths in weighted graphs, such as in network routing, road navigation systems, etc.

Output:

{ NC,12-4-60,4-16-30#16-17-15#17-18-20, NC }

 



Dijsktra Shortest Path for directed graph
Dijsktra Shortest Path for directed graph






Tags:

Post a Comment

1 Comments

Post a Comment