Algorytm Dijkstry

Poziom trudności Średni
Często zadawane pytania Accolita Adobe Amazonka Cisco Interaktywne rozwiązania Morgan Stanley Samsung Vizury
Algorytm Dijkstry Wykres Chciwy Najkrótsza droga Teoriaodwiedzajacy 163

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Dijkstra to algorytm najkrótszej ścieżki. Algorytm Dijkstry służy do znalezienia najkrótszej odległości wszystkich węzłów od danego węzła początkowego. Logicznie rzecz biorąc, tworzy drzewo najkrótszej ścieżki z pojedynczego węzła źródłowego, poprzez zachłanne dodawanie węzłów w taki sposób, że w każdym punkcie każdy węzeł w drzewie ma minimalną odległość od danego węzła początkowego.

Algorytm Dijkstry jest chciwy podejście, które wykorzystuje bardzo prosty fakt matematyczny do wyboru węzła na każdym kroku.

„Dodanie dwóch liczb dodatnich zawsze da w wyniku liczbę większą niż oba dane wejściowe”.

Algorytm

Oto algorytm Dijkstry

Używane zmienne

  1. n: liczba węzłów.
  2. e: liczba krawędzi.
  3. odwiedził, tablica o rozmiarze n służąca do śledzenia węzłów dodawanych do drzewa.
  4. koszt, tablica o rozmiarze n do przechowywania minimalnego kosztu dotarcia do ith od węzła początkowego poprzez prawidłową ścieżkę w drzewie.

Cel

  1. Zainicjuj odwiedzoną tablicę wartością false, która pokazuje, że obecnie drzewo jest puste.
  2. Inicjalizuj tablicę kosztów z nieskończonością, która pokazuje, że nie jest możliwe dotarcie do żadnego węzła z węzła początkowego poprzez prawidłową ścieżkę w drzewie.
  3. Koszt dotarcia do węzła początkowego zawsze będzie wynosił zero, stąd koszt [start] = 0.
  4. Teraz przy każdej iteracji wybieramy węzeł do dodania w drzewie, dlatego potrzebujemy n iteracji, aby dodać n węzłów w drzewie:
    • Wybierz węzeł, który ma minimalny koszt i jest obecnie nie odwiedzany, tj. Nie ma go w drzewie.
    • Zaktualizuj koszt nieodwiedzonych węzłów, które sąsiadują z nowo dodanym węzłem, o minimum poprzedniej i nowej ścieżki.
    • Oznacz węzeł jako odwiedzony.

Przykład algorytmu Dijkstry

Mając wykres, obliczyć minimalną odległość wszystkich węzłów od punktu A jako węzła początkowego.

algorytm dijkstraszpilka

Rozwiązanie krok po kroku algorytmu Dijkstry

algorytm dijkstraszpilka
1. Odległość A od A wynosi 0

 

algorytm dijkstraszpilka
2. Odległość C od A wynosi 1

 

algorytm dijkstraszpilka
3. Odległość D od A wynosi 3

 

szpilka
4. Odległość B od A wynosi 3

 

szpilka
5. Odległość E od A wynosi 7

Wada algorytmu Dijkstry

Jak wiemy, podstawową właściwością zastosowaną w Dijkstrze jest dodanie dwóch liczb dodatnich, stąd algorytm ten może prowadzić do błędnej odpowiedzi w przypadku wykresu zawierającego ujemne krawędzie.

Przykład

Rozważ wykres

szpilka

Węzeł początkowy:

Dijkstra obliczy 3 jako minimalną odległość do osiągnięcia B z punktu A.

Ale wyraźnie widzimy, że droga A-> C-> E-> B będzie kosztować 2, aby dotrzeć do B z A.

Pytanie o algorytm Dijkstry

Biorąc pod uwagę ukierunkowany wykres ważony z n węzłami i e krawędziami, Twoim zadaniem jest znalezienie minimalnego kosztu dotarcia do każdego węzła z danego węzła początkowego

Wkład

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n (liczba krawędzi) ie (liczba krawędzi).

Kolejne e wiersze zawierają trzy liczby całkowite oddzielone spacjami u, v i w, gdzie:

  • u: węzeł źródłowy
  • v: węzeł docelowy
  • w: waga krawędzi

Ostatnia linia zawiera s, oznaczające węzeł początkowy

ograniczenia

1 <= n <= 1000

0 <= e <= (n * (n-1)) / 2

1 <= waga <= 103

Wykres nie zawiera pętli samoczynnej i wielu krawędzi.

Kod C ++ dla algorytmu Dijkstry

#include<bits/stdc++.h>
#define INF INT_MAX
using namespace std;

// Function to find the non-visited node which is at minimum distance
int findMin(int n,int cost[],bool visited[]){
    int min=INF;
    int node=0;
    for(int i=0;i<n;i++){
        if(visited[i]==false && min>cost[i]){
            min=cost[i];
            node=i;
        }
    }
    return node;
}
void dijkstra(int n, vector<pair<int,int>> graph[], int start){
    bool visited[n];    // to specify which nodes are yet to visit
    int cost[n];            // cost[i] specifies the minimum cost to reach ith node from start node through visited nodes
    for(int i=0;i<n;i++){
        cost[i]=INF;                          // initialize cost array with INFINITY
                                             // to signify that all nodes are non-reachable initially
        visited[i]=false;                     // initialize visited array with false 
                                             // to signify that all nodes are non-visited initially
    }
    
    cost[start]=0;                           // minimum cost to reach the start node will be zero
    int count=0;                             // count will keep track of how many nodes are visited till now
    
    while(count<n){
        int node = findMin(n,cost,visited);
        visited[node]=true;
        for(auto &i:graph[node]){
            if(visited[i.first]==false){
                cost[i.first]=min(cost[i.first],cost[node]+(i.second));
            }
        }
        count++;
    }
    
    for(int i=0;i<n;i++){
        cout<<"Distance of node "<<i<<" from node "<<start<<" is "<<cost[i]<<"\n";
    }
}
int main(){
    int n,e;
    cin>>n>>e;
    vector<pair<int,int>> graph[n];
    for(int i=0;i<e;i++){
        int u,v,w;
        cin>>u>>v>>w;
        graph[u].push_back(make_pair(v,w));
        graph[v].push_back(make_pair(u,w));
    }
    int start;
    cin>>start;
    dijkstra(n,graph,start);
}
5 7
0 2 5
0 1 3
2 3 2
3 4 5
2 4 1
4 1 4
2 3 7
0
Distance of node 0 from node 0 is 0
Distance of node 1 from node 0 is 3
Distance of node 2 from node 0 is 5
Distance of node 3 from node 0 is 7
Distance of node 4 from node 0 is 6

Kod Java dla algorytmu Dijkstry

import java.util.Scanner;


public class Main {
  public static int [][] graph;
  public static int [] visited;
  public static int [] cost;
  public static int start;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n,e, INF = Integer.MAX_VALUE;
      n = sc.nextInt();
      e = sc.nextInt();
      
      graph = new int [n][n];
      visited = new int [n];
      cost = new int[n];
        
      for (int i = 0; i < n; i++) {			
        for (int j = 0; j < n; j++) {
          graph[i][j] = -1;
        }
      }
      
      for (int i = 0; i < e; i++) {
        int u = sc.nextInt();
        int v = sc.nextInt();
        int w = sc.nextInt();
        graph[u][v] = w;
        graph[v][u] = w;
      }
      
      start = sc.nextInt();
      
      for (int i = 0; i < n; i++) {
        cost[i]=INF;
      }
      cost[start]=0;
      
      dijkstra(start);
      printResult();
    }
  
  /* Recursive function to find the minimum distance of each node from given start node*/
  public static void dijkstra(int start){
    for (int i = 0; i <cost.length; i++) {
      if (graph[start][i] > -1 && cost[i] > (graph[start][i] + cost[start]) ){
        cost[i] = graph[start][i] + cost[start];
      }
    }
    
    int j = minDist();
    if (j  == -1 )
      return;
    
    visited[j] = 1;
    dijkstra(j);		
  }
  
  /* Function to print the distance of each node from given start node*/
  public static void printResult(){
    for (int i = 0; i <cost.length; i++) {
    		System.out.println("Distance of node "+i+" from node "+start+" is "+cost[i]);
    }
  }
  
  /* Function to find non-visited node with minimum distance*/
  public static int minDist(){
    int minDistance = Integer.MAX_VALUE;
    int index = -1; 
    for (int i=0; i<cost.length; i++){
      if (minDistance>cost[i] && visited[i] == 0){
        minDistance = cost[i];
        index = i;				
      }
    }
    return index;
  }

}
Input:
4 5
0 1 12
0 3 24
2 0 3
1 3 10
3 2 12
0
Output:
Distance of node 0 from node 0 is 0
Distance of node 1 from node 0 is 12
Distance of node 2 from node 0 is 3
Distance of node 3 from node 0 is 15

Złożoność czasowa: O (n * n)

Złożoność czasową algorytmu Dijkstry można poprawić za pomocą stosu binarnego w celu wybrania węzła przy minimalnym koszcie (krok 4)

Numer Referencyjny

Przejdź przez więcej pytania podczas rozmowy kwalifikacyjnej

Wywiady dotyczące projektowania systemu pękania
Translate »