迪杰斯特拉最短路径算法

迪杰斯特拉最短路径算法与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的分配距离，例如d₁，其中d₁ < ∞。

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

示例

为了更好地理解迪杰斯特拉的概念，让我们借助一个示例图来分析该算法 -

步骤1

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

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

visited = {S}

步骤2

顶点S有三个具有不同距离的相邻顶点，其中最小距离的顶点是A。因此，访问A并将dist[A]从∞更改为6。

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

Visited = {S, 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

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] = 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

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

步骤6

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

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

使用迪杰斯特拉算法获得最短路径生成树作为输出。

示例

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

#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