迪杰斯特拉(Dijkstra)算法求最短路径

落日映苍穹つ 2022-02-13 10:27 295阅读 0赞

## 1.Dijkstra算法原理 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70][]

## ##

（1）两个顶点集 S 、T = V - S（V是原图所有顶点集合）

S：存放已找到最短路径的顶点

T：存放未找到最短路径的顶点

（2）实现步骤：

先将开始节点（V0）加入 S，不断从 T 中选取到 V0 有最短路径的顶点 （u），将 u 加入 S；S 中每加入一个顶点都要修改 V0 到 T 中剩余顶点的最短路径长度值。直到 T 中顶点全部加入 S。

<table style="width:700px;"> 
 <tbody> 
 <tr> 
 <td colspan="1">终点</td> 
 <td colspan="5">V0 到各终点的 D 值和最短路径求解过程</td> 
 </tr> 
 <tr> 
 <td>i = 1</td> 
 <td>i = 2</td> 
 <td>i = 3</td> 
 <td>i = 4</td> 
 <td>i = 5</td> 
 </tr> 
 <tr> 
 <td>V1</td> 
 <td> D[1] =&nbsp;<img alt="\infty" src="https://private.codecogs.com/gif.latex?%5Cinfty"> p[1] = {0,0,0,0,0,0} </td> 
 <td><img alt="\infty" src="https://private.codecogs.com/gif.latex?%5Cinfty"></td> 
 <td><img alt="\infty" src="https://private.codecogs.com/gif.latex?%5Cinfty"></td> 
 <td><img alt="\infty" src="https://private.codecogs.com/gif.latex?%5Cinfty"></td> 
 <td><img alt="\infty" src="https://private.codecogs.com/gif.latex?%5Cinfty"></td> 
 </tr> 
 <tr> 
 <td>V2</td> 
 <td> D[2] = 10 p[2] = {1,0,1,0,0,0} 即&lt;V0，V2&gt; </td> 
 <td>&nbsp;</td> 
 <td>&nbsp;</td> 
 <td>&nbsp;</td> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td>V3</td> 
 <td> D[3] =&nbsp;<img alt="\infty" src="https://private.codecogs.com/gif.latex?%5Cinfty"> p[3] = {0,0,0,0,0,0} </td> 
 <td> D[3] = 60 p[3] = {1,0,1,1,0,0} 即&lt;V0，V2，V3&gt; </td> 
 <td> D[3] = 50 p[3]&nbsp;= {1,0,0,1,1,0} 即&lt;V0，V4，V3&gt; </td> 
 <td>&nbsp;</td> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td>V4</td> 
 <td> D[4] = 30 p[4] = {1,0,0,0,1,0} 即&lt;V0，V4&gt; </td> 
 <td> D[4] = 30 p[4] = {1,0,0,0,1,0} 即&lt;V0，V4&gt; </td> 
 <td>&nbsp;</td> 
 <td>&nbsp;</td> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td>V5</td> 
 <td> D[5] = 100 p[5] = {1,0,0,0,0,1} 即&lt;V0，V5&gt; </td> 
 <td> D[5] = 100&nbsp; p[5] = {1,0,0,0,0,1} 即&lt;V0，V5&gt; </td> 
 <td> D[5] = 90 p[5] = {1,0,0,0,1,1} 即&lt;V0，V4，V5&gt; </td> 
 <td> D[5] = 60 p[5] = {1,0,0,1,1,1} 即&lt;V0，V4，V3，V5&gt; </td> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td>Vj</td> 
 <td>V2</td> 
 <td>V4</td> 
 <td>V3</td> 
 <td>V5</td> 
 <td>&nbsp;</td> 
 </tr> 
 <tr> 
 <td>S</td> 
 <td>{V0，V2}</td> 
 <td>{V0，V2，V4}</td> 
 <td>{V0，V2，V4，V3}</td> 
 <td>{V0，V2，V4，V3，V5}</td> 
 <td>&nbsp;</td> 
 </tr> 
 </tbody> 
</table>

## 2.源代码 ##

### 2.1 Java实现 ###

package math_problem;
 
 import java.util.Arrays;
 import java.util.Scanner;
 
 class Graph {
 static final int MAX_VEX_NUM = 20; // 最大顶点数
 char[] vertex = new char[MAX_VEX_NUM]; // 顶点数组
 int graphType; // 图的类型。1-有向图，0-无向图
 int vexNum; // 实际顶点数
 int edgeNum; // 实际边数
 int[][] edgeWeight = new int[MAX_VEX_NUM][MAX_VEX_NUM]; // 保存边的权值
 }
 
 public class ShortestPathDemo {
 static Scanner input = new Scanner(System.in);
 static final int INFINITY = 65535; // 边上最大权值
 
 private static int getIndexOfChar(char[] charArray, char c) {
 for (int i = 0; i < charArray.length; i++) {
 if (c == charArray[i])
 return i;
 }
 return -1;
 }
 
 private void createGraph(Graph g) {
 int weight;
 char sVex, eVex;// 边的起始、结束顶点
 
 System.out.print("创建图，请输入图的类型（1：有向图/0：无向图)：");
 g.graphType = input.nextInt();
 
 System.out.println("创建图，请输入各顶点信息...");
 System.out.print("请输入顶点数量：");
 g.vexNum = input.nextInt();
 for (int l = 0; l < g.vexNum; l++) {
 System.out.printf("第 %d 个顶点：", l+1);
 g.vertex[l] = (input.next().toCharArray())[0];
 }
 
 System.out.println("创建图，请输入各边顶点及权值...");
 System.out.print("请输入边数量：");
 g.edgeNum = input.nextInt();
 
 // 初始化邻接矩阵
 for (int i = 0; i < g.vexNum; i++) {
 for (int j = 0; j < g.vexNum; j++) {
 g.edgeWeight[i][j] = INFINITY;
 }
 }
 
 System.out.println("请依次输入每条边的信息(起始顶点，结束顶点，权值)：");
 int indexOfsVex, indexOfeVex;
 for (int i = 0; i < g.edgeNum; i++) {
 sVex = input.next().charAt(0);
 eVex = input.next().charAt(0);
 weight = input.nextInt();
 
 indexOfsVex = getIndexOfChar(g.vertex, sVex);
 indexOfeVex = getIndexOfChar(g.vertex, eVex);
 g.edgeWeight[indexOfsVex][indexOfeVex] = weight;
 // 若是无向图，保存边 E（k，j）的权值
 if (g.graphType == 0) {
 g.edgeWeight[indexOfeVex][indexOfsVex] = weight;
 }
 }
 }
 
 // 输出邻接矩阵
 private void displayAdjMatrix(Graph g) {
 int i, j;
 
 // 先输出顶点信息
 for (i = 0; i < g.vexNum; i++) {
 System.out.printf("\t%c", g.vertex[i]);
 }
 System.out.println();
 
 // 输出邻接矩阵
 for (j = 0; j < g.vexNum; j++) {
 System.out.printf("%c", g.vertex[j]);
 for (i = 0; i < g.vexNum; i++) {
 if (g.edgeWeight[j][i] == INFINITY) {
 // 权值大于等于最大权值时，输出无穷大的符号
 System.out.print("\t∞");
 continue;
 }
 System.out.printf("\t%d", g.edgeWeight[j][i]);
 }
 System.out.println();
 }
 }
 
 private static void dijkstraShortestPath(Graph g) {
 int minWeight, indexOfsVex, k = 0;
 char startVex;
 int[] d = new int[g.vexNum];
 int[] s = new int[g.vexNum];
 int[][] p = new int[g.vexNum][g.vexNum];
 
 System.out.print("请输入开始节点：");
 startVex = input.next().charAt(0);
 indexOfsVex = getIndexOfChar(g.vertex, startVex);
 
 for (int i = 0; i < g.vexNum; i++) {
 d[i] = g.edgeWeight[indexOfsVex][i];
 if (d[i] < INFINITY) {
 p[i][indexOfsVex] = 1;
 p[i][i] = 1;
 }
 }
 // 将起始节点加入集合 S
 s[indexOfsVex] = 1;
 
 for (int i = 1; i < g.vexNum; i++) {
 minWeight = INFINITY;
 for (int j = 0; j < g.vexNum; j++) {
 if (s[j] != 1 && d[j] < minWeight) {
 minWeight = d[j];
 k = j;
 }
 }
 // 将新的节点加入集合 S
 s[k] = 1;
 
 for (int j = 0; j < g.vexNum; j++) {
 if (s[j] != 1 && (minWeight + g.edgeWeight[k][j] < d[j])) {
 d[j] = minWeight + g.edgeWeight[k][j];
 for (int l = 0; l < g.vexNum; l++) {
 p[j][l] = p[k][l];
 }
 p[j][j] = 1;
 }
 }
 }
 
 for (int i = 0; i < g.vexNum; i++) {
 for (int j = 0; j < g.vexNum; j++) {
 System.out.print(p[i][j] + " ");
 }
 System.out.println();
 }
 
 System.out.println(Arrays.toString(d));
 }
 
 public static void main(String[] args) {
 Graph graph = new Graph();
 ShortestPathDemo demo = new ShortestPathDemo();
 demo.createGraph(graph);
 demo.displayAdjMatrix(graph);
 demo.dijkstraShortestPath(graph);
 }
 }

创建图，请输入图的类型（1：有向图/0：无向图)：1
    创建图，请输入各顶点信息...
    请输入顶点数量：6
    第 1 个顶点：0
    第 2 个顶点：1
    第 3 个顶点：2
    第 4 个顶点：3
    第 5 个顶点：4
    第 6 个顶点：5
    创建图，请输入各边顶点及权值...
    请输入边数量：8
    请依次输入每条边的信息(起始顶点，结束顶点，权值)：
    0 2 10
    0 4 30
    0 5 100
    4 5 60
    4 3 20
    3 5 10
    2 3 50
    1 2 5
    	0	1	2	3	4	5
    0	∞	∞	10	∞	30	100
    1	∞	∞	5	∞	∞	∞
    2	∞	∞	∞	50	∞	∞
    3	∞	∞	∞	∞	∞	10
    4	∞	∞	∞	20	∞	60
    5	∞	∞	∞	∞	∞	∞
    请输入开始节点：0
    0 0 0 0 0 0 
    0 0 0 0 0 0 
    1 0 1 0 0 0 
    1 0 0 1 1 0 
    1 0 0 0 1 0 
    1 0 0 1 1 1 
    [65535, 65535, 10, 50, 30, 60]
    
    Process finished with exit code 0

### 2.2 C语言实现  ###

#include <stdio.h>
 #include <stdlib.h>
 
 #define INFINITY 10000 /* 假定弧上权值无穷大时为10000 */
 #define MAX_VERTEX_NUM 100 /* 图中最大节点数 */
 typedef char VexType; /* 顶点类型设置为字符型 */
 typedef int weight; /* 弧上权值类型设置为整型 */
 typedef struct /* 弧表节点 */
 {
 VexType vex[MAX_VERTEX_NUM]; /* 图中节点 */
 weight edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/* 邻接矩阵 */
 int vexnum; /* 节点的数目 */
 int edgenum; /* 弧的数目 */
 }MGraph;
 
 void CreateDG(MGraph * DG); /* 邻接矩阵法创建有向图（directed graph） */
 void PrintDG(MGraph DG); /* 邻接矩阵形式输出图DG */
 void ShortestPath_Dijkstra(MGraph DG, VexType StartVex);
 /* 从节点StartVex开始求最短路径 */
 void locateVex(MGraph DG, VexType vex, int * index);
 /* 定位节点vex的下标并赋给index */ 
 
 int main(void)
 {
 MGraph g;
 
 CreateDG(&g);
 printf("------------------------------\n");
 printf("vexnum = %d ; edgenum = %d\n", g.vexnum, g.edgenum);
 printf("------------------------------\n");
 PrintDG(g);
 printf("------------------------------\n");
 ShortestPath_Dijkstra(g, '0');
 
 return 0;
 }
 void CreateDG(MGraph * DG)
 {
 int i = 0, j, k, w; /* w：权值 */
 char ch;
 
 printf("请依次输入顶点数、弧数：");
 scanf("%d %d", &(DG->vexnum), &(DG->edgenum));
 
 printf("请依次输入顶点（以回车结束输入）：");
 getchar();
 while ((ch = getchar()) != '\n') /* 输入顶点信息 */
 DG->vex[i++] = ch;
 
 for (i = 0; i < DG->vexnum; i++) /* 初始化邻接矩阵 */
 for (j = 0; j < DG->vexnum; j++)
 DG->edges[i][j] = INFINITY;
 
 printf("顶点 | 下标\n");
 for (i = 0; i < DG->vexnum; i++) /* 显示图中顶点及其对应下标 */
 {
 printf("%3c%6d\n", DG->vex[i], i);
 }
 
 printf("请输入依次每条弧的弧尾下标(不带箭头)、弧头下标(带箭头)、权值（格式：i j w）：\n");
 for (k = 0; k < DG->edgenum; k++) /* 建立邻接矩阵 */
 {
 scanf("\n%d%d%d", &i, &j, &w); /* 输入弧的两个节点及权值 */
 DG->edges[i][j] = w; /* 将矩阵对应位置元素置为权值 */
 }
 }
 void PrintDG(MGraph DG)
 {
 int i, j;
 
 for (i = 0; i < DG.vexnum; i++) /* 输出邻接矩阵 */
 {
 for (j = 0; j < DG.vexnum; j++)
 {
 if (DG.edges[i][j] == INFINITY) /* 节点不连通时，输出无穷大 */
 printf(" ∞");
 else /* 节点连通时，输出弧上权值 */
 printf("%5d", DG.edges[i][j]);
 }
 printf("\n");
 }
 }
 void ShortestPath_Dijkstra(MGraph DG, VexType StartVex)
 {
 int i, j, v, index; /* index：开始节点下标 */
 int min; /* 开始节点到指定节点的最短路径权值和 */
 int final[DG.vexnum]; /* 集合S，元素值为1：下标为i的节点以加入集合S；为0：未加入 */
 int P[DG.vexnum][DG.vexnum];/* 开始节点到各节点的最短路径 */
 int D[DG.vexnum]; /* 开始节点到下标为i的节点的最短路径权值之和 */
 
 locateVex(DG, StartVex, &index);
 for (i = 0; i < DG.vexnum; i++)
 {
 final[i] = 0; /* 初始化，刚开始集合S为空 */
 D[i] = DG.edges[index][i];
 
 for (j = 0; j < DG.vexnum; j++) /* 初始化路径，假设所有节点都不连通 */
 P[i][j] = 0;
 if (D[i] < INFINITY) /* 若节点连通，则在数组P[i]中标明路径 */
 {
 P[i][index] = 1;
 P[i][i] = 1;
 }
 }
 D[index] = 0; final[index] = 1; /* 开始节点加入S集 */
 
 for (i = 1; i < DG.vexnum; i++)
 {
 min = INFINITY;
 for (j = 0; j < DG.vexnum; j++)
 if (!final[j])
 if (D[j] < min) { v = j; min = D[j]; }
 final[v] = 1; /* 把离StartVex最近的下标为v的节点加入S */ 
 
 for (j = 0; j < DG.vexnum; j++)
 if (!final[j] && (min + DG.edges[v][j] < D[j]))
 {/* 若下标为j的节点为加入S且有更短路径，则更新D[j]和最短路径 */
 D[j] = min + DG.edges[v][j];
 for (int k = 0; k < DG.vexnum; k++)
 P[j][k] = P[v][k];
 P[j][j] = 1;
 }
 }
 
 printf("节点 %c 到各节点的最短路径：\n", StartVex);
 for (i = 0; i < DG.vexnum; i++) 
 {
 for (j = 0; j < DG.vexnum; j++)
 printf("%5d", P[i][j]);
 printf("\n");
 }
 
 printf("节点 %c 到各节点的最短路径值：", StartVex);
 for (i = 0; i < DG.vexnum; i++)
 {
 if (D[i] == INFINITY)
 printf("∞, ");
 else
 printf("%d, ", D[i]); 
 }
 }
 void locateVex(MGraph DG, VexType vex, int * index)
 {
 int i;
 
 for (i = 0; i < DG.vexnum; i++)
 {
 if (DG.vex[i] == vex)
 {
 *index = i;
 return;
 }
 }
 printf("节点定位失败！\n");
 }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]: /images/20220213/f72fc0c9b65f45c7952b7acfc49ee425.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1]: /images/20220213/cf570d3c4e6b4179acb2d44f8217b8dc.png