图——单源最短路径（三）加权有向无环图中的最短路径算法

时间：2024-04-03 14:48:12

图——单源最短路径（三）加权有向无环图中的最短路径算法

在许多应用中的加权有向图都是不包含有向环的，因此对于这些图可以采用一种将拓扑排序和顶点的放松结合起来的算法，该算法与Dijkstra算法之间的区别：
（1）比Dijkstra算法更快且更简单的最短路径算法，该算法是；
（2）Dijkstra算法要求加权有向图中的边的权重非负，而该算法能够处理负权重的边。

1. 算法思想

目标
对于一个无环加权有向图 G=(V,E)G=(V, E) ，现在要求其中的结点S到其他各结点的最短路径。假设用 sdis[k]sdis[k] 表示结点k到结点S的最短路径长度，用 lastnode[k]lastnode[k] 表示结点k在从节点S到节点k的最短路径上的前驱结点。

算法思路
该算法的处理过程如下：
（1）初始化
将 sdis[S]sdis[S] 初始化为0，将图中其他结点 k∈V−Sk\in V-S 的 sdis[k]sdis[k] 初始化为无穷大；将 lastnode[S]lastnode[S] 初始化为S，将图中其他结点 k∈V−Sk\in V-S 的 lastnode[k]lastnode[k] 初始化为0（假设结点标号从1开始，所以0则表示没有前驱结点）。
（2）对加权有向图进行拓扑排序；
（3）从拓扑排序的源点开始，对拓扑排序序列进行遍历，直到找到结点S。在结点S前的结点都是从结点S无法到达的结点，所以其最短路径长度都为无穷大。
（4）从结点S开始，一个个安装拓扑顺序放松所有顶点。

算法分析
Dijkstra算法的时间复杂度为Θ(V2)\Theta(V^2) ，而该算法的时间复杂度为Θ(V+E)\Theta(V+E)，它能够在线性的时间内解决单点最短路径问题，也能处理负权重的边。

2. 算法实现

2.1 数据结构

由于该算法要进行拓扑排序，所以此处用邻接链表来表示图：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<map>
#include<vector>
#include<sstream>
#include<list>
#include<stdlib.h>
#include<queue>
#include<algorithm>
#include<stack>
using namespace std;

#define Maximum 1000
#define Biggest 1000000

typedef struct EdgeListNode{  //边表
    int adjId;
    int weight;
    EdgeListNode* next;
};

typedef struct VertexListNode{  //顶点表
    int data;
    int in;  //顶点的入度
    EdgeListNode* firstadj;
};

typedef struct GraphAdjList{
    int vertexnumber;
    int edgenumber;
    VertexListNode vertextlist[Maximum];
};

2.2 代码实现

void Topologically_Sort(GraphAdjList g, int *sorted_path) {
    int i, j, k, index;
    stack<int>zero;
    EdgeListNode *e;

    while(!zero.empty()) {
        zero.pop();
    }

    for(i=1; i<=g.vertexnumber; i++) {
        if(g.vertextlist[i].in == 0) {
            zero.push(i);
        }
    }

    index = 0;
    while(!zero.empty()) {
        j = zero.top();
        zero.pop();
        sorted_path[index++] = j;

        e = g.vertextlist[j].firstadj;
        while(e!=NULL) {
            g.vertextlist[e->adjId].in--;
            if(g.vertextlist[e->adjId].in == 0) {
                zero.push(e->adjId);
            }
            e = e->next;
        }
    }
}

void DAG_SHORTEST_PATHS(GraphAdjList g, int s, int *sdis, int *lastnode) {
    int i, j, k, l;
    EdgeListNode *edge;

    int *sorted_path = (int*)malloc(sizeof(int)*(g.vertexnumber + 2));
    for(i=1; i<= g.vertexnumber; i++) {
        sdis[i] = Biggest;
        lastnode[i] = 0;
    }
    Topologically_Sort(g, sorted_path);


    for(i=0; i<g.vertexnumber; i++) {
        if(sorted_path[i] == s) {
            break;
        }
    }

    sdis[s] = 0; lastnode[s] = s;
    for(j=i; j<g.vertexnumber; j++) {
        k = sorted_path[j];
        edge = g.vertextlist[k].firstadj;
        while(edge != NULL) {
            l = edge->adjId;
            if(sdis[l] > sdis[k] + edge->weight) {
                sdis[l] = sdis[k] + edge->weight;
                lastnode[l] = k;
            }
            edge = edge->next;
        }
    }
}

2.3 测试

测试的图如下：
图——单源最短路径（三）加权有向无环图中的最短路径算法

测试代码：

int main() {
    GraphAdjList g;
    EdgeListNode *temp;

    g.edgenumber = 6;
    g.vertexnumber = 4;

    g.vertextlist[1].in = 0;
    g.vertextlist[1].firstadj = NULL;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 2; temp->weight = 1; temp->next = g.vertextlist[1].firstadj;
    g.vertextlist[1].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 3; temp->weight = 2; temp->next = g.vertextlist[1].firstadj;
    g.vertextlist[1].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 4; temp->weight = 8; temp->next = g.vertextlist[1].firstadj;
    g.vertextlist[1].firstadj = temp;

    g.vertextlist[2].in = 1;
    g.vertextlist[2].firstadj = NULL;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 3; temp->weight = 3; temp->next = g.vertextlist[2].firstadj;
    g.vertextlist[2].firstadj = temp;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 4; temp->weight = 2; temp->next = g.vertextlist[2].firstadj;
    g.vertextlist[2].firstadj = temp;


    g.vertextlist[3].in = 2;
    g.vertextlist[3].firstadj = NULL;

    temp = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    temp->adjId = 4; temp->weight = 1; temp->next = g.vertextlist[3].firstadj;
    g.vertextlist[3].firstadj = temp;

    g.vertextlist[4].in = 3;
    g.vertextlist[4].firstadj = NULL;



    int *sdis = (int*)malloc(sizeof(int)*(g.vertexnumber+2));
    int *lastnode = (int*)malloc(sizeof(int)*(g.vertexnumber+2));
    DAG_SHORTEST_PATHS(g, 1, sdis, lastnode);

    int i = 4;
    cout<<sdis[i]<<endl;

    while(i != 1) {
        cout<<i<<"  ";
        i = lastnode[i];
    }
    cout<<1<<endl;


    return 0;
}

相关文章