### Shortest Path from source to Vertex :- Dijkstra Algorithm

Shortest Path from source to Vertex :- Dijkstra Algorithm:-

Dijkstra Algorithms is an algorithm use to find the shortest path from source vertex to a given vertex.

```package Graph;

import java.util.HashMap;

abstract public class DirectedGraph {

Vertex[] vertexlist=new Vertex;
HashMap<Character,HashMap<Character,Integer>> edgelist=new HashMap<>();
Vertex vertex;
//count of vertex and edge
static int vertexcount=0;
int edgecount=0;
/*
* This function takes a label and insert in the vertex list as well as edge list since it is new vertex it will add
* null to its adjoining vertices
*/
{
vertex=new Vertex(label);
vertexlist[vertexcount]=vertex;
System.out.println(vertexlist[vertexcount].label);
edgelist.put(vertex.label, null);
vertexcount++;
return vertexcount;
}

{
HashMap<Character,Integer> vertexlist=new HashMap<>();
for(int i=0;i<labels.length;i++)
{
vertexlist.put(labels[i], distances[i]);
}
edgelist.put(label, vertexlist);
return edgecount;
}

int removeEdge(char labelfrom,char labelto)
{
edgelist.get(labelfrom).remove(labelto);
edgecount--;
return edgecount;
}

HashMap<Character,Integer> getNeighbours(char label)
{
return edgelist.get(label);
}

void listOfVertex()
{
System.out.println("Total Vertex:"+ vertexcount);

//This is how we traverse over a hashmap
for(Object key:edgelist.keySet())
{
System.out.println(key+" " +edgelist.get(key));
}

}
}
```

```package Graph;

import java.util.HashMap;
import java.util.Queue;
import java.util.Stack;

public class DirectedGraphImpl extends DirectedGraph {

//Algorithm to search the shortest path
public void djiksta(DirectedGraphImpl g)
{
//Creating new instance of grapg passed in parameter
DirectedGraphImpl newgraph=new DirectedGraphImpl();
newgraph=g;

/*
* Declaring hashmap for holding vertex value in character and distance from source in Integer
*/
HashMap<Character,Integer> map=new HashMap<>();
/*
* Declaring queue to iterate graph in BFS fashion
*/

//Initializing new instance of graph with vertex and distance as minimum value
for(int i=0;i<newgraph.vertexcount;i++)
{
map.put(vertexlist[i].label, Integer.MIN_VALUE);
}

while(!queue.isEmpty())
{
//checking vertex distance if it minimum distance make it as 0
if(map.get(queue.peek())==Integer.MIN_VALUE)
{
map.put(queue.peek(), 0);
}

//Storing previous vertex name
char previousvertex=queue.peek();

//Getting neigbours of previous vertex as well as removing the same from queue tail
HashMap<Character,Integer> neigbours=newgraph.getNeighbours(queue.remove());

//if neighbours are there
if(neigbours!=null)
{

//iterating over neighbours
for(Character key:neigbours.keySet())
{
//Adding neighbour in queue from front

/*
* checking condition if distance(new vertex from previous vertex)+distance(source to previous vertex)
* is less than what we have in able assign new distance to the table
*
*
* supose from A to B distance is 4
* from A to C distance is 1 and from C to A distance is 2 then
*
*  A to B 4 will be replaced by 3
*/
int newvalue=neigbours.get(key)+map.get(previousvertex);

//loop will only run when distance is less or distance not yet defined
if(newvalue<map.get(key) || map.get(key)==Integer.MIN_VALUE)
{
map.put((Character) key, newvalue);
}

}
}

}

//calling method to show final matrix of Vertex distance relation
showShortestDistance(map);

}

//Iterating Hash Map to show the shortest distance of vertex from Source
public void showShortestDistance(HashMap map)
{
for(Object key:map.keySet())
{
System.out.println(key.toString()+"    "+map.get(key));
}
}

public static void main(String[] args)
{
DirectedGraphImpl dgraph=new DirectedGraphImpl();

dgraph.listOfVertex();
System.out.println("shortest distance in a graph using djikstra");
dgraph.djiksta(dgraph);

}

}
```

### Dynamic Programming in JAVA

StringLongest common subsequencelongest increasing subsequencelongest common substringedit distanceGraphsbellman fordfloyd's all pair shortestchain matrix multiplicationsubset sum0/1 knapsackTravelling salesman problem