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

2023-11-01 22:38:22

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

0x00 前言

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

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

0x01 代码分析

#include<stdio.h>
#define MAXVEX 10
int 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");
}

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

码农公寓