В алгоритме кратчайшего пути Дейкстры с одним источником мы пытаемся найти кратчайшее расстояние от одного источника до всех остальных узлов в неориентированном графе.
Примечание: Мы не можем использовать технику, которую мы использовали ранее для нахождения кратчайшего расстояния в неориентированном графе, где вес ребра составлял 1 единицу. Так как здесь вес ребра может быть любым числом, следовательно, этот подход будет неудачным.
Что такое алгоритм Дейкстры?
В основном, мы начинаем с исходного узла и переходим ко всем узлам, убеждаясь, что все узлы достижимы при наименьшем возможном расстоянии от исходного.
Например
Решение: Временная сложность составляет приблизительно o(n+nlogn) (если предположить, что ребра e = количество узлов n). n для первого обхода графа в ширину и nlogn для использования приоритетной очереди для сортировки в порядке возрастания расстояния.
Пространственная сложность составляет o(n) + o(n) (для массива расстояний и очереди приоритетов).
//User function Template for Java
class Pair{
int key;
int value;
public Pair(){}
public Pair(int i, int j ){
this.key=i;
this.value = j;
}
public int getKey(){
return this.key;
}
public int getValue(){
return this.value;
}
}
class Solution
{
//Function to find the shortest distance of all the vertices
//from the source vertex S.
static int[] dijkstra(int V, ArrayList<ArrayList<ArrayList<Integer>>> adj, int S)
{// we will use breadth first search for getting shortest path of all the nodes from
// source.
int distance[] = new int[V];
Arrays.fill(distance,Integer.MAX_VALUE);//initially all the distances are unknown from the source hence Integer.MAX_VALUE;
distance[S] = 0;//distance of source from source is 0
//since we take the not visited node with the smallest distance from the source(according to the Dijkstra's algorithm) hence
//this priority queue is needed that sorts the entries accordingly
//key = node, value = distance from the source
PriorityQueue<Pair> q = new PriorityQueue<>((a,b)->a.getValue()-b.getValue());
// adding the source node as the smallest distance node from the source (S,0)
q.add(new Pair(S,0));
while(!q.isEmpty()){
Pair p = q.remove();
for(ArrayList<Integer> l : adj.get(p.getKey())){
//for example u--->v (source--->adjacentNode)
// if() => distance[v]> dist(u,v) + valueOF(u); where valueOF(u) means cost to reach u from source
if(distance[l.get(0)]>l.get(1) + p.getValue()){
distance[l.get(0)] = l.get(1)+p.getValue(); // now this distace[v] has been calculated we can put
//it inside priority queue..
q.add(new Pair(l.get(0),distance[l.get(0)]));
}
}
}
return distance;//finally we can return distance;Integer.MAX_VALUE; it means that it is not reachable from the source node
}
}