Dijkstra 的最短路径算法

Dijkstra 的最短路径算法与 Prim 的算法类似，都是依靠局部寻找最短路径来实现全局解。然而，与 prim 算法不同的是，dijkstra 算法并没有找到最小生成树；它的目的是找到图中从一个顶点到图中其他剩余顶点的最短路径。Dijkstra 算法可以在有向图和无向图上执行。

由于可以计算出图中从单个源顶点到所有其他顶点的最短路径，因此 Dijkstra 算法也称为单源最短路径算法。获得的输出称为最短路径生成树。

在本章中，我们将学习迪杰斯特拉算法的贪婪方法。

迪杰斯特拉算法

dijkstra 算法旨在找到图的两个顶点之间的最短路径。这两个顶点可以是图中相邻的点或最远的点。算法从源头开始。该算法的输入是图G {V，E}，其中V是顶点集，E是边集，以及源顶点S。输出是最短路径生成树。

算法

• 声明两个数组 - distance [] 来存储从源顶点到图中其他顶点的距离，visited [] 来存储访问过的顶点。

• 将距离[S] 设置为“0”，距离[v] = ∞，其中 v 表示图中的所有其他顶点。

• 将S添加到visited[]数组中，并找到S中距离最小的相邻顶点。

• 与 S 相邻的顶点（例如 A）具有最小距离，并且尚未位于访问数组中。A 被选取并添加到访问数组中，A 的距离从 ∞ 更改为 A 的指定距离，例如 d ₁，其中 d ₁ < Infini。

• 对访问过的顶点的相邻顶点重复该过程，直到形成最短路径生成树。

例子

为了更好地理解 dijkstra 的概念，让我们借助示例图来分析该算法 -

步骤1

将除源节点 S 之外的所有顶点的距离初始化为 ∞。

现在源顶点S已被访问，将其添加到visited数组中。

visited = {S}

第2步

顶点S有3个距离不同的相邻顶点，其中距离最小的顶点都是A。因此，访问A，dist[A]从无穷大变为6。

S → A = 6
S → D = 8
S → E = 7

Visited = {S, A}

步骤3

访问数组中有两个访问过的顶点，因此必须检查两个访问过的顶点的相邻顶点。

顶点 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

Visited = {S, A, E}

步骤4

计算所有访问数组的相邻顶点（S、A、E）的距离，并选择距离最小的顶点。

S → D = 8
S → B = 15
S → C = S → E + E → C = 7 + 5 = 12

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] = 最小值 (12, 11) = 11

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

距离[B] = 最小值 (15,23) = 15

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

步骤6

图中剩余的未访问顶点是 B，最小距离为 15，被添加到输出生成树中。

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

使用 dijkstra 算法获得最短路径生成树作为输出。

例子

该程序实现了迪杰斯特拉最短路径问题，该问题以成本邻接矩阵作为输入，并打印最短路径作为输出以及最小成本。

#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