Finding shortest path in a unidrectional weighted graph in java can be achieved in multiple ways.

In this article, I will demonstrate a very basic Dynamic Programming approach, in which we will simply keep a track of the shortestPath for each node, and will consecutively update all the connected nodes with this information.

We can start with assiging the root or starting point to be as of 0, and the criteria to update any further connected node will be - if a node is connected and the already shortest path to reach there is greater than what we can achieve by migrating from the current node + the edge weight between the current node and the connected node.

To keep it simple, I am also using edge as a list of maps - representing what nodes are connected to all the vertices and with what weight. Key of the map is vertex index of connected node, and value is weight.

            0
     /2     |1       \2     
   1        2          3
            |      1/  \3
           1|       4      5
            |   1/      /
            |    /      /1
              6  

Here's the implementation:

import java.util.*;
public class Main
{
    static class Graph
    {
        int[] v;
        int n;
        List<Integer, Map<Integer, Integer>> edges;
        public Graph(int n){
            this.n=n;
            v=new int[n];
            edges=new ArrayList<Integer>(n);
            for(int i=0;i<n;i++){
                edges.add(new HashMap<>());
            }
        }
        public void addEdge(int a,int b, int weight){
            edges.get(a).put(b,weight);
        }
        public int shortest(int a,int b){
            int[] minToReach = new int[n];
            for(int i=0;i connected = edges.get(i);
                for(Integer node:connected.keySet()){
                    int ed = connected.get(node);
                    if(minToReach[node]>minToReach[i]+ed){
                        minToReach[node] = minToReach[i]+ed;
                    }
                }
            }
            for(int i=0;i<=b;i++){
                System.out.println(i+" => "+minToReach[i]);
            }
            return minToReach[b];
        }
    }
	public static void main(String[] args) {
		Graph g=new Graph(7);
		g.addEdge(0,1,2);
		g.addEdge(0,2,1);
		g.addEdge(0,3,2);
		g.addEdge(2,6,1);
		g.addEdge(3,4,1);
		g.addEdge(3,5,3);
		g.addEdge(4,6,1);
		g.addEdge(5,6,1);
		System.out.println(g.shortest(0,6));
	}
}

If you run this program, it will print the shortest path to each node, and at the end will print the required result , shortest path from 0 to 6th node. 0 => 0
1 => 2
2 => 1
3 => 2
4 => 3
5 => 5
6 => 2

2