Dijkstra 最短路径算法

更新于 2025/10/16 16:21:06

Dijkstra 算法
示例

Dijkstra 最短路径算法与 Prim 算法类似，因为它们都依赖于在局部寻找最短路径来实现全局解。然而，与 Prim 算法不同，Dijkstra 算法并非寻找最小生成树；它旨在寻找图中从一个顶点到其他顶点的最短路径。迪杰斯特拉算法既可以在有向图上运行，也可以在无向图上运行。

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

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

迪杰斯特拉算法

迪杰斯特拉算法旨在查找图中两个顶点之间的最短路径。这两个顶点可以是相邻的，也可以是图中距离最远的点。该算法从源开始。该算法的输入是图 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₁ < ∞。
对已访问顶点的相邻顶点重复此过程，直到形成最短路径生成树。

示例

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

步骤 1

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

Vertex	S	A	B	C	D	E
Distance	0	∞	∞	∞	∞	∞

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

visited = {S}

步骤 2

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

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

Vertex	S	A	B	C	D	E
Distance	0	6	∞	∞	8	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

Vertex	S	A	B	C	D	E
Distance	0	6	15	∞	8	7

Visited = {S, A, E}

步骤 4

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

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

Vertex	S	A	B	C	D	E
Distance	0	6	15	12	8	7

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] = minimum (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] = minimum (15,23) = 15

Vertex	S	A	B	C	D	E
Distance	0	6	15	11	8	7

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

步骤 6

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

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[]){ // 寻找最小距离
   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; // 源顶点 dist 设置为 0
   for(int k = 0; k<6; k++) {
      int m=min_dist(dist,visited);
      visited[m]=true;
      for(int k = 0; k<6; k++) {

         // 更新相邻顶点的距离
         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		dist from source vertex
");
   for(int k = 0; k<6; k++) {
      char str=65+k;
      printf("%c			%d
", 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[]){ // 寻找最小距离
   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; // 源顶点 dist 设置为 0
   for(int k = 0; k<6; k++) {
      int m=min_dist(dist,visited);
      visited[m]=true;
      for(int k = 0; k<6; k++) {

         // 更新相邻顶点的距离
         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		dist from source vertex"<<endl;
   for(int k = 0; k<6; k++) {
      char str=65+k;
      cout<<str<<"			"<<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[]) { // 寻找最小距离
      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; // 源顶点 dist 设置为 0
      for (int k = 0; k < 6; k++) {
         int m = min_dist(dist, visited);
         visited[m] = true;
         for (int j = 0; j < 6; j++) {
            // 更新相邻顶点的距离
            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		dist from source vertex");
      for (int k = 0; k < 6; k++) {
         char str = (char) (65 + k);
         System.out.println(str + "			" + 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):  # 寻找最小距离
    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  # 源顶点 dist 设置为 0
    for _ in range(6):
        m = min_dist(dist, visited)
        visited[m] = True
        for k in range(6):
            #  更新相邻顶点的距离
            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		dist from source vertex")
    for k in range(6):
        str_val = chr(65 + k)  # 将索引转换为对应的字符
        print(str_val, "			", 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

数据结构和算法

数据结构

链接列表

堆栈 &队列

搜索算法

排序算法

图形数据结构

树数据结构

递归

分而治之

贪婪算法

动态规划

近似算法

随机算法

DSA 有用资源

Dijkstra 最短路径算法

迪杰斯特拉算法

算法

示例

示例

输出

输出

输出

输出

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！