原 初学图论-DAG单源最短路径算法

    当图中没有环时,使用Bellman-Ford这一低效算法显然就不划算了,这时我们可以选择DAG算法。

    本文使用C++实现了这一基本算法。参考《算法导论》第24.2节

    笔者使用了vector实现邻接链表,以提高运行效率。

/**
 * DAG's Single Source Shortest Path Algorithm in C++
 * Based on DFS, don't let any circle exist in the graph
 * Time Cost : O(|N|+|M|)
 * Introduction to Algorithms (CLRS) 24.2
 * Author: Zheng Chen / Arclabs001
 * Copyright 2015 Xi'an University of Posts & Telecommunications
 */
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
#define INF 0xfffffff
using namespace std;
const int N = 6;
const int M = 10;
ifstream in;

enum status {UNDISCOVERED,DISCOVERED,VISITED};

struct edge
{
    int dest;
    int weight;
};

struct vertex
{
    int num;
    int dist;
    int inDegree,outDegree;
    status _stat;
    vertex * parent;
}V[N];

vector<edge> AdjList[N];
stack<int> vertexStack;   //The call srack
stack<int> topo_order;
int t;

void initialize(int s)
{
    for(int i=0; i<N; i++)
    {
        V[i].num = i;
        V[i].dist = INF;
        V[i].parent = nullptr;
        V[i].inDegree = 0;
        V[i].outDegree = 0;
        V[i]._stat = UNDISCOVERED;
        AdjList[i].clear();
    }

    for(int i=0; i<M; i++)  //Read informations of edges and insert into the Adjacent List
    {
        int _start, _dest, _weight;
        edge * tmp = new edge;

        in>>_start>>_dest>>_weight;
        tmp->dest = _dest;
        tmp->weight = _weight;
        V[_start].outDegree++;
        V[_dest].inDegree++;

        AdjList[_start].push_back(*tmp);
    }

    V[s].dist = 0;
    t = 0;
}

void relax(int u, int v, int weight)  //The "relax" operation
{
    if(V[v].dist > V[u].dist + weight)
    {
        V[v].dist = V[u].dist + weight;
        V[v].parent = &V[u];
    }
}
/**
 * The main dfs-visit function, to get the topo-order of the graph
 * @param i [the root of each tree]
 */
void dfs_Visit(int i)
{
    V[i]._stat = DISCOVERED;

    edge tmp;
    for(int j=0; j<V[i].outDegree; j++)
    {
        tmp = AdjList[i][j];
        if(V[tmp.dest]._stat == UNDISCOVERED)
        {
            dfs_Visit(tmp.dest);
        }
    }

    V[i]._stat = VISITED;
    topo_order.push(i);
}

void topo_sort()
{
    for(int i=0; i<N; i++)
    {
        if(V[i]._stat == UNDISCOVERED)
        {
            dfs_Visit(i);
        }
    }
}

void DAG_shortest_path(int s)
{
    initialize(s);
    topo_sort();

    while(!topo_order.empty())
    {
        edge tmp;
        int tmp_vertex = topo_order.top();
        //cout<<"Now stack top is : "<<topo_order.top()<<endl;
        topo_order.pop();

        for(int j=0; j<V[tmp_vertex].outDegree; j++)
        {
            tmp = AdjList[tmp_vertex][j];
            relax(tmp_vertex,tmp.dest,tmp.weight);
        }
    }
}

void print_path(vertex *s, vertex *v)
{
    if(v == s)
        cout<<s->num;
    else if(v->parent == nullptr)
        cout<<"No path from "<<s->num<<" to "<<v->num<<endl;
    else
    {
        print_path(s,v->parent);
        cout<<"->"<<v->num;
    }
}

int main()
{
    in.open("DAG.txt");
    int s = 1;
    DAG_shortest_path(s);

    cout<<"Succeed ! The distance of each vertex are :"<<endl;
    for(int i=0; i<N; i++) if(V[i].dist == INF) cout<<"INF "; else cout<<V[i].dist<<" ";

    cout<<endl<<"One of the shortest path is :"<<endl;
    print_path(&V[1],&V[5]);
    return 0;
}

/*
Pseudo-Code :
DAG-SHORTEST-PATHS(G,w,s)
    topologically sort the vertices of G
    Initialize-Single-Source(G,s)
    for each vertex u, taken in topologically sorted order
        for each vertex v in Adj[u]
            Relax(v,u,w)
 */

//DAG.txt文件内容如下:

0 1 5

0 2 3

1 2 2

1 3 6

2 3 7

2 4 4

2 5 2

3 4 -1

3 5 1

4 5 -2

每一行的三个元素分别表示某条边的起始节点、终止节点、这条边的权重。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏lhyt前端之路

从MDN上的canvas例子受到的启发0.前言1.面向对象编程的实践2.相互纠缠的现象3.解决方案4.模拟核裂变5.大鱼吃小鱼

在面对碰撞检测后还有后续动作的情况,必须考虑一下相互纠缠的问题: 如果两个小球被检测到碰撞的时候,而且加上他们的速度下一步还是处于碰撞范围内,就像引力一样无法脱...

1422
来自专栏聊聊技术

原 "二分查找(Binary Search

43011
来自专栏数据结构与算法

1405 奶牛的旅行

题目描述 Description 农民John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言,你能看到至少有两个...

2898
来自专栏深度学习之tensorflow实战篇

igraph软件包创建图和网络(创建邻接矩阵)

一、igraph软件包创建图和网络 igraph 是一个独立的库,底层是 C,上层有 Python 和 R 接口,主要做图和网络方面的计算,附带绘图功能。 ...

6154
来自专栏java 成神之路

java.util.Random 实现原理

3375
来自专栏LhWorld哥陪你聊算法

【推荐系统篇】--推荐系统之训练模型

经过之前的训练数据的构建可以得到所有特征值为1的模型文件,本文将继续构建训练数据特征并构建模型。

1731
来自专栏一英里广度一英寸深度的学习

Intellij idea配置Spark开发环境,统计哈姆雷特词频(2)

中间层Spark,即核心模块Spark Core,必须在maven中引用。 编译Spark还要声明java8编译工具。

2132
来自专栏从流域到海域

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

迪杰斯特拉(Dijkstra )算法: 对于图G=(V,E),将图的顶点分为两组: 顶点集S:已求出的最短路径的顶点集合(初始为{v0}); 顶...

2227
来自专栏xingoo, 一个梦想做发明家的程序员

Spark源码分析之分区器的作用

最近因为手抖,在Spark中给自己挖了一个数据倾斜的坑。为了解决这个问题,顺便研究了下Spark分区器的原理,趁着周末加班总结一下~ 先说说数据倾斜 数据...

24010
来自专栏决胜机器学习

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(1)

PHP数据结构(十一)——图的连通性问题与最小生成树算法(1) (原创内容,转载请注明来源,谢谢) 一、连通分量和生成树 1、无向图 设E(G)为连通图G的所...

4669

扫码关注云+社区

领取腾讯云代金券