聊一聊利用 Dijkstra 求有向图的最短路径

关注

发布于: 1 小时前

聊一聊利用 Dijkstra 求有向图的最短路径

0x00 前言

我们都知道求最短路径有很多方法，比如 Dijkstra 算法、Bellman-Ford 算法、Floyd-Warshall 算法等等，这些算法各有优缺点，其中 Floyd-Warshall 算法时间复杂度较高，但是编码复杂度较小，而 Bellman-Ford 算法适用于处理有负权边的情况。至于本文要讲的 Dijkstra 算法，优点就是时间复杂度较小，但是不能处理有负权边的图。

我们需要根据不同情况选择不同的算法。

0x01 代码分析

#include<stdio.h>#define MAXVEX 10int graph[MAXVEX][MAXVEX];int short_path[MAXVEX];int prev_v[MAXVEX];

复制代码

先导入标准输入输出库，我们将节点数设置为 10 个，然后设置存储图的 graph、存储源点到其他各点的最短路径长度的 short_path，还有存储最短路径上各节点的前置节点的 prev_v。

1. 建图

void create_graph( void ){  for(int i=0;i<10;i++){    for(int j=0;j<10;j++){      if(i==j){        graph[i][j]=0;        continue;      }      graph[i][j] = 99999;    }  }  printf("请输入有向边的条数:");  int n;  scanf("%d",&n);  for(int k=0;k<n;k++){    int i,j,value;    scanf("%d %d %d",&i,&j,&value);    graph[i][j]=value;  }}

复制代码

然后就是将图初始化了。这里我们将没个顶点到自己的距离初始化为 0，然后将其他点先全部初始化为 99999，然后在给每条边赋权值。

2. 求最短路径

void Dijkstra(int g[10][10], int v0) {  int final[MAXVEX];  int j = 0;  int k = 0;  for(j = 0; j<MAXVEX; j++) {     final[j] = 0;    short_path[j] = g[v0][j];    prev_v[j] = 0;  }  final[v0] = 1;   short_path[v0] = 0;      for(int i = 1; i < MAXVEX; i++) {     int min = MAXVEX;    k = 0;    for(int j=0; j<MAXVEX; j++) {      if(final[j]==0 && short_path[j]<min) {        min = short_path[j];        k = j;      }    }    final[k] = 1;             for(int j=0; j<MAXVEX; j++) {      if(final[j]==0 && min+g[k][j] < short_path[j]) {        short_path[j] = min+g[k][j];        prev_v[j] = k;      }    }  }}

复制代码

大餐来了，迪杰斯特拉算法来了！

该函数传入的参数是图和源点。

我们使用一个数组来标记是否源点到该点已经找出了最短路径。

再将 final、short_path、prev_v 初始化，将 v0 的所有边加入 short_path。

因为源点到源点的最短距离已经确定了是 0，所以我们将 final[v0]标记为 1，short_path[v0]标记为 0。

然后接下来的第一个循环表示一共需要找 MAXVEX-1 条最短路径，然后从源点到剩余未被标记的顶点中寻找最短的一条路径。然后将找到的下一个点标记，表示源点到该点的路径已经找到。然后看一看源点到其它各顶点（尚未确定最短路径的顶点）的最短路径中，如果途经顶点 k 的路径长度比原路径更短,就更新。并设置 k 为 j 的前置节点。

3. 输出最短路径

void show_shortest_path( int source ,int end) {  int que[10];  int tot = 1;  printf("source到%d的最短路径: ",end);  que[tot] = end;  tot++;
  int i = prev_v[end];  while(i != source) {    que[tot] = i;    tot++;    i = prev_v[i];  }  que[tot] = source;  for(int i=tot;i>=1;i--){    if(i!=1){      printf("%d->",que[i]);    }else{      printf("%d",que[i]);    }      }  printf("\n");}

复制代码

就是建一个数组当作队列，然后将每次找到的节点放到队列中，然后顺序遍历。

发布于: 1 小时前阅读数: 3

原文链接:【http://xie.infoq.cn/article/07a8b10398a7b356bf77bd7d7】。

Regan Yue

关注

还未添加个人签名 2020.08.12 加入

对Go、Python、网络安全、区块链感兴趣. · 华为云云享专家 · 掘金资讯创作者

发布

暂无评论

创作场景

聊一聊利用 Dijkstra 求有向图的最短路径

聊一聊利用 Dijkstra 求有向图的最短路径

0x00 前言

0x01 代码分析

1. 建图

2. 求最短路径

3. 输出最短路径

Regan Yue

评论