迪傑斯特拉最短路徑演算法

Table of content
上一頁
下一頁

迪傑斯特拉最短路徑演算法與Prim演算法類似，它們都依賴於區域性查詢最短路徑來實現全域性解。但是，與Prim演算法不同，迪傑斯特拉演算法不會找到最小生成樹；它旨在找到圖中從一個頂點到圖中其他剩餘頂點的最短路徑。迪傑斯特拉演算法可以應用於有向圖和無向圖。

由於可以計算從單個源頂點到圖中所有其他頂點的最短路徑，因此迪傑斯特拉演算法也稱為單源最短路徑演算法。獲得的輸出稱為最短路徑生成樹。

在本章中，我們將學習迪傑斯特拉演算法的貪心策略。

迪傑斯特拉演算法

迪傑斯特拉演算法旨在找到圖中兩個頂點之間的最短路徑。這兩個頂點可以是相鄰的，也可以是圖中最遠的點。演算法從源點開始。演算法的輸入是圖G {V, E}，其中V是頂點集，E是邊集，以及源頂點S。輸出是最短路徑生成樹。

演算法

  • 宣告兩個陣列 - distance[] 用於儲存從源頂點到圖中其他頂點的距離，以及visited[] 用於儲存已訪問的頂點。

  • 將distance[S]設定為‘0’，並將distance[v] = ∞，其中v表示圖中所有其他頂點。

  • 將S新增到visited[]陣列中，並找到S的具有最小距離的相鄰頂點。

  • S的相鄰頂點，例如A，具有最小距離，並且尚未在visited陣列中。選擇A並將其新增到visited陣列中，並將A的距離從∞更改為A的分配距離，例如d1，其中d1 < ∞。

  • 對已訪問頂點的相鄰頂點重複此過程，直到形成最短路徑生成樹。

示例

為了更好地理解迪傑斯特拉的概念，讓我們藉助一個示例圖來分析該演算法 -

Dijkstras graph

步驟1

將所有頂點的距離初始化為∞，除了源節點S。

頂點 S A B C D E
距離 0 ∞ ∞ ∞ ∞ ∞

現在源頂點S已被訪問，將其新增到visited陣列中。

visited = {S}

步驟2

頂點S有三個具有不同距離的相鄰頂點，其中最小距離的頂點是A。因此，訪問A並將dist[A]從∞更改為6。

S → A = 6
S → D = 8
S → E = 7
頂點 S A B C D E
距離 0 6 ∞ ∞ 8 7 
Visited = {S, A}
Visited s to a

步驟3

visited陣列中有兩個頂點已被訪問，因此必須檢查這兩個已訪問頂點的相鄰頂點。

頂點S還有兩個尚未訪問的相鄰頂點：D和E。頂點A有一個相鄰頂點B。

計算從S到D、E、B的距離，並選擇最小距離 -

S → D = 8 and S → E = 7.
S → B = S → A + A → B = 6 + 9 = 15
頂點 S A B C D E
距離 0 6 15 ∞ 8 7 
Visited = {S, A, E}
Visited_S_A_E

步驟4

計算所有已訪問陣列的相鄰頂點 - S、A、E - 的距離，並選擇距離最小的頂點。

S → D = 8
S → B = 15
S → C = S → E + E → C = 7 + 5 = 12
頂點 S A B C D E
距離 0 6 15 12 8 7 
Visited = {S, A, E, D}
Visited_s_a_e_d

步驟5

重新計算未訪問頂點的距離，如果找到比現有距離小的距離，則替換距離陣列中的值。

S → C = S → E + E → C = 7 + 5 = 12
S → C = S → D + D → C = 8 + 3 = 11

dist[C] = min(12, 11) = 11

S → B = S → A + A → B = 6 + 9 = 15
S → B = S → D + D → C + C → B = 8 + 3 + 12 = 23

dist[B] = min(15,23) = 15

頂點 S A B C D E
距離 0 6 15 11 8 7 
Visited = { S, A, E, D, C}
Visited_S_A_E_D_C

步驟6

圖中剩餘的未訪問頂點是B，距離最小為15，將其新增到輸出生成樹中。

Visited = {S, A, E, D, C, B}
Visited_S_A_E_D_C_B

使用迪傑斯特拉演算法獲得最短路徑生成樹作為輸出。

示例

該程式實現了迪傑斯特拉最短路徑問題，該問題以成本鄰接矩陣作為輸入，並列印最短路徑以及最小成本作為輸出。

C C++ Java Python
#include<stdio.h>
#include<limits.h>
#include<stdbool.h>
int min_dist(int[], bool[]);
void greedy_dijsktra(int[][6],int);
int min_dist(int dist[], bool visited[]){ // finding minimum dist
   int minimum=INT_MAX,ind;
   for(int k=0; k<6; k++) {
      if(visited[k]==false && dist[k]<=minimum) {
         minimum=dist[k];
         ind=k;
      }
   }
   return ind;
}
void greedy_dijsktra(int graph[6][6],int src){
   int dist[6];
   bool visited[6];
   for(int k = 0; k<6; k++) {
      dist[k] = INT_MAX;
      visited[k] = false;
   }
   dist[src] = 0; // Source vertex dist is set 0
   for(int k = 0; k<6; k++) {
      int m=min_dist(dist,visited);
      visited[m]=true;
      for(int k = 0; k<6; k++) {

         // updating the dist of neighbouring vertex
         if(!visited[k] && graph[m][k] && dist[m]!=INT_MAX && dist[m]+graph[m][k]<dist[k])
            dist[k]=dist[m]+graph[m][k];
      }
   }
   printf("Vertex\t\tdist from source vertex\n");
   for(int k = 0; k<6; k++) {
      char str=65+k;
      printf("%c\t\t\t%d\n", str, dist[k]);
   }
}
int main(){
   int graph[6][6]= {
      {0, 1, 2, 0, 0, 0},
      {1, 0, 0, 5, 1, 0},
      {2, 0, 0, 2, 3, 0},
      {0, 5, 2, 0, 2, 2},
      {0, 1, 3, 2, 0, 1},
      {0, 0, 0, 2, 1, 0}
   };
   greedy_dijsktra(graph,0);
   return 0;
}

輸出

Vertex		dist from source vertex
A			   0
B			   1
C			   2
D			   4
E			   2
F			   3

#include<iostream>
#include<climits>
using namespace std;
int min_dist(int dist[], bool visited[]){ // finding minimum dist
   int minimum=INT_MAX,ind;
   for(int k=0; k<6; k++) {
      if(visited[k]==false && dist[k]<=minimum) {
         minimum=dist[k];
         ind=k;
      }
   }
   return ind;
}
void greedy_dijsktra(int graph[6][6],int src){
   int dist[6];
   bool visited[6];
   for(int k = 0; k<6; k++) {
      dist[k] = INT_MAX;
      visited[k] = false;
   }
   dist[src] = 0; // Source vertex dist is set 0
   for(int k = 0; k<6; k++) {
      int m=min_dist(dist,visited);
      visited[m]=true;
      for(int k = 0; k<6; k++) {

         // updating the dist of neighbouring vertex
         if(!visited[k] && graph[m][k] && dist[m]!=INT_MAX && dist[m]+graph[m][k]<dist[k])
            dist[k]=dist[m]+graph[m][k];
      }
   }
   cout<<"Vertex\t\tdist from source vertex"<<endl;
   for(int k = 0; k<6; k++) {
      char str=65+k;
      cout<<str<<"\t\t\t"<<dist[k]<<endl;
   }
}
int main(){
   int graph[6][6]= {
      {0, 1, 2, 0, 0, 0},
      {1, 0, 0, 5, 1, 0},
      {2, 0, 0, 2, 3, 0},
      {0, 5, 2, 0, 2, 2},
      {0, 1, 3, 2, 0, 1},
      {0, 0, 0, 2, 1, 0}
   };
   greedy_dijsktra(graph,0);
   return 0;
}

輸出

Vertex		dist from source vertex
A			   0
B			   1
C			   2
D			   4
E			   2
F			   3

public class Main {
   static int min_dist(int dist[], boolean visited[]) { // finding minimum dist
      int minimum = Integer.MAX_VALUE;
      int ind = -1;
      for (int k = 0; k < 6; k++) {
         if (!visited[k] && dist[k] <= minimum) {
            minimum = dist[k];
            ind = k;
         }
      }
      return ind;
   }
   static void greedy_dijkstra(int graph[][], int src) {
      int dist[] = new int[6];
      boolean visited[] = new boolean[6];
      for (int k = 0; k < 6; k++) {
         dist[k] = Integer.MAX_VALUE;
         visited[k] = false;
      }
      dist[src] = 0; // Source vertex dist is set 0
      for (int k = 0; k < 6; k++) {
         int m = min_dist(dist, visited);
         visited[m] = true;
         for (int j = 0; j < 6; j++) {
            // updating the dist of neighboring vertex
            if (!visited[j] && graph[m][j] != 0 && dist[m] != Integer.MAX_VALUE
                  && dist[m] + graph[m][j] < dist[j])
               dist[j] = dist[m] + graph[m][j];
         }
      }
      System.out.println("Vertex\t\tdist from source vertex");
      for (int k = 0; k < 6; k++) {
         char str = (char) (65 + k);
         System.out.println(str + "\t\t\t" + dist[k]);
      }
   }
   public static void main(String args[]) {
      int graph[][] = { { 0, 1, 2, 0, 0, 0 }, { 1, 0, 0, 5, 1, 0 }, { 2, 0, 0, 2, 3, 0 },
            { 0, 5, 2, 0, 2, 2 }, { 0, 1, 3, 2, 0, 1 }, { 0, 0, 0, 2, 1, 0 } };
      greedy_dijkstra(graph, 0);
   }
}

輸出

Vertex		dist from source vertex
A			0
B			1
C			2
D			4
E			2
F			3

import sys
def min_dist(dist, visited):  # finding minimum dist
    minimum = sys.maxsize
    ind = -1
    for k in range(6):
        if not visited[k] and dist[k] <= minimum:
            minimum = dist[k]
            ind = k
    return ind
def greedy_dijkstra(graph, src):
    dist = [sys.maxsize] * 6
    visited = [False] * 6
    dist[src] = 0  # Source vertex dist is set 0
    for _ in range(6):
        m = min_dist(dist, visited)
        visited[m] = True
        for k in range(6):
            #  updating the dist of neighbouring vertex
            if not visited[k] and graph[m][k] and dist[m] != sys.maxsize and dist[m] + graph[m][k] < dist[k]:
                dist[k] = dist[m] + graph[m][k]
    print("Vertex\t\tdist from source vertex")
    for k in range(6):
        str_val = chr(65 + k)  # Convert index to corresponding character
        print(str_val, "\t\t\t", dist[k])
# Main code
graph = [
    [0, 1, 2, 0, 0, 0],
    [1, 0, 0, 5, 1, 0],
    [2, 0, 0, 2, 3, 0],
    [0, 5, 2, 0, 2, 2],
    [0, 1, 3, 2, 0, 1],
    [0, 0, 0, 2, 1, 0]
]
greedy_dijkstra(graph, 0)

輸出

Vertex		dist from source vertex
A 			 0
B 			 1
C 			 2
D 			 4
E 			 2
F 			 3
列印頁面
上一頁
下一頁
廣告