How to find the shortest path of nodes in java....?

Question

We have 8 nodes in the 2 paths to reach the destination we have to find which one path is the shortest.. ???

Mukil Vendhan · Answer

In Pseudocode, Dijkstra’s algorithm can be translated like that : check this code: package com.ssaurel.dijsktra; public class Edge { private int fromNodeIndex; private int toNodeIndex; private int length; public Edge( int fromNodeIndex, int toNodeIndex, int length) { this .fromNodeIndex = fromNodeIndex; this .toNodeIndex = toNodeIndex; this .length = length; } public int getFromNodeIndex() { return fromNodeIndex; } public int getToNodeIndex() { return toNodeIndex; } public int getLength() { return length; } // determines the neighbouring node of a supplied node, based on the two nodes connected by this edge public int getNeighbourIndex( int nodeIndex) { if ( this .fromNodeIndex == nodeIndex) { return this .toNodeIndex; } else { return this .fromNodeIndex; } } }

Manikandan Murugesan · Answer

Like SplinterReality said: There's no reason not to use Dijkstra's algorithm here. import java.util.PriorityQueue; import java.util.List; import java.util.ArrayList; import java.util.Collections; class Vertex implements Comparable { public final String name; public Edge[] adjacencies; public double minDistance = Double.POSITIVE_INFINITY; public Vertex previous; public Vertex(String argName) { name = argName; } public String toString() { return name; } public int compareTo(Vertex other) { return Double.compare(minDistance, other.minDistance); } } class Edge { public final Vertex target; public final double weight; public Edge(Vertex argTarget, double argWeight) { target = argTarget; weight = argWeight; } } public class Dijkstra { public static void computePaths(Vertex source) { source.minDistance = 0 .; PriorityQueue vertexQueue = new PriorityQueue (); vertexQueue.add(source); while (!vertexQueue.isEmpty()) { Vertex u = vertexQueue.poll(); // Visit each edge exiting u for (Edge e : u.adjacencies) { Vertex v = e.target; double weight = e.weight; double distanceThroughU = u.minDistance + weight; if (distanceThroughU vertexQueue.remove(v); v.minDistance = distanceThroughU ; v.previous = u; vertexQueue.add(v); } } } } public static List getShortestPathTo(Vertex target) { List path = new ArrayList (); for (Vertex vertex = target; vertex != null ; vertex = vertex.previous) path.add(vertex); Collections.reverse(path); return path; } public static void main(String[] args) { // mark all the vertices Vertex A = new Vertex( "A" ); Vertex B = new Vertex( "B" ); Vertex D = new Vertex( "D" ); Vertex F = new Vertex( "F" ); Vertex K = new Vertex( "K" ); Vertex J = new Vertex( "J" ); Vertex M = new Vertex( "M" ); Vertex O = new Vertex( "O" ); Vertex P = new Vertex( "P" ); Vertex R = new Vertex( "R" ); Vertex Z = new Vertex( "Z" ); // set the edges and weight A.adjacencies = new Edge[]{ new Edge(M, 8 ) }; B.adjacencies = new Edge[]{ new Edge(D, 11 ) }; D.adjacencies = new Edge[]{ new Edge(B, 11 ) }; F.adjacencies = new Edge[]{ new Edge(K, 23 ) }; K.adjacencies = new Edge[]{ new Edge(O, 40 ) }; J.adjacencies = new Edge[]{ new Edge(K, 25 ) }; M.adjacencies = new Edge[]{ new Edge(R, 8 ) }; O.adjacencies = new Edge[]{ new Edge(K, 40 ) }; P.adjacencies = new Edge[]{ new Edge(Z, 18 ) }; R.adjacencies = new Edge[]{ new Edge(P, 15 ) }; Z.adjacencies = new Edge[]{ new Edge(P, 18 ) }; computePaths(A); // run Dijkstra System.out.println( "Distance to " + Z + ": " + Z.minDistance); List path = getShortestPathTo(Z); System.out.println( "Path: " + path); } } The code above produces: Distance to Z : 49.0 Path : [ A , M , R , P , Z ]

Zakir Ahamed · Answer

follow this link http://stackoverflow.com/questions/35730843/path-between-2-nodes-using-bfs

How to find the shortest path of nodes in java....?

Answers (3)