精华内容
下载资源
问答
  • 单源最短路

    2019-11-26 19:53:27
    单源最短路 文字描述 准备: 我们开一个数组dis(int类型)记录各结点与源点的距离和一个数组vis(bool类型)记录各个结点的访问情况 初始化: 我们将dis数组全赋值为inf(不可能达到的最长距离, 0x3f3f3f3f或者0x3f3f3f3f3...

    单源最短路

    文字描述

    准备: 我们开一个数组dis(int类型)记录各结点与源点的距离和一个数组vis(bool类型)记录各个结点的访问情况

    初始化: 我们将dis数组全赋值为inf(不可能达到的最长距离, 0x3f3f3f3f或者0x3f3f3f3f3f3f3f3f),然后将dis1赋值为0,然后将vis全部赋值为false

    操作: 每次遍历所有结点,找到未访问结点中与源点距离最小的(也就是vis任然为false且dis最小的)并将这个结点对应的vis更新为true,然后我们遍历从这个结点出发的所有边并更新dis(如果我们找到的结点是x且存在一条从x到y距离为s的路径,则我们进行操作dis[y] = min(dis[y], dis[x]+s) )。

    重复操作直到所有结点的vis都为true为止

    代码实现

    #include<map>
    #include<queue>
    #include<string>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    struct road{
        int to, distance;
    
        road(){}
        road(int to, int distance): to(to), distance(distance){}
    };
    
    const int maxn = 25;
    const int inf = 0x3f3f3f3f;
    int dis[maxn], precursor[maxn];
    bool vis[maxn];
    map<char, int> node_to_num;
    char num_to_node[maxn];
    queue<road> node[maxn];
    
    void data_in(int &node_num) {
        string str_node;
        int road_num, start_node, end_node, distance;
        cin >> node_num >> road_num >> str_node;
    
        // 记录数字对应字母结点和字母结点对应的数字
        for(int i = 0; i < node_num; i++) num_to_node[i+1] = str_node[i], node_to_num[str_node[i]] = i+1;
    
        // 申请临时储存线路的矩阵并全赋值为0
        int **dis_matrix = new int*[node_num+1];
        for(int i = 0; i <= node_num; i++) dis_matrix[i] = new int[node_num+1]();
    
        for(; road_num; road_num--) {
            cin >> str_node >> distance;
            start_node = node_to_num[str_node[0]];
            end_node = node_to_num[str_node[1]];
            node[start_node].push(road(end_node, distance));
            dis_matrix[start_node][end_node] = distance;
        }
    
        // 输出初始线路
        cout << endl << "====================================================" << endl;
        cout << "对应矩阵为:" << endl << setw(5) << "";
        for(int i = 1; i <= node_num; i++) cout << setw(5) << num_to_node[i];
        for(int i = 1; i <= node_num; i++) {
            cout << endl << setw(5) << num_to_node[i];
            for(int j = 1; j <= node_num; j++) (i == j || dis_matrix[i][j]) ? cout << setw(5) << dis_matrix[i][j]: cout << setw(5) << "inf";
        }
    
        // 释放
        for(int i = 0; i <= node_num; i++) {
            delete[] dis_matrix[i];
            dis_matrix[i] = nullptr;
        }
        delete[] dis_matrix;
        dis_matrix = nullptr;
    }
    
    void init(const int source, const int node_num) {
        for(int i = 0; i <= node_num; i++) dis[i] = inf, vis[i] = false, precursor[i] = source;
        dis[source] = 0; precursor[source] = 0;
    }
    
    void calculate(const int node_num) {
        while(true) {
            int min_dis = 0;
            for(int i = 1; i <= node_num; i++) if(!vis[i] && dis[i] < dis[min_dis]) min_dis = i;
            if(!min_dis) return;
            vis[min_dis] = true;
            while(!node[min_dis].empty()) {
                road tmp = node[min_dis].front(); node[min_dis].pop();
                if(dis[tmp.to] > dis[min_dis]+tmp.distance) {
                    // 最短路更新时不要忘记更新前驱
                    dis[tmp.to] = dis[min_dis]+tmp.distance;
                    precursor[tmp.to] = min_dis;
                }
            }
        }
    }
    
    void path_out(int node_i) {
        if(precursor[node_i]) {
            path_out(precursor[node_i]);
            cout << setw(5) << "-->" << setw(3) << num_to_node[node_i];
        } else cout << setw(3) << num_to_node[node_i];
    }
    
    void data_out(const int node_num) {
        cout << endl << "====================================================" << endl;
        cout << "最短路径为:" << endl;
        for(int i = 2; i <= node_num; i++) {
            path_out(i);
            dis[i] == inf? cout << "无路径" << endl: cout << "长度" << dis[i] << endl;
        }
    }
    
    int main() {
        int source = 1, node_num;
        cout << left;
        data_in(node_num);
        init(source, node_num);
        calculate(node_num);
        data_out(node_num);
        return 0;
    }
    
    /*
    6 8
    ABCDEF
    AC 10
    AE 30
    AF 100
    BC 5
    CD 50
    DF 10
    ED 20
    EF 60
    */
    
    展开全文
  • 单源最短路算法

    2013-06-04 17:25:28
    dijstra单源最短路+详细注释,类似宽搜
  • 文章目录求解单源最短路的Dijkstra算法算法描述解集dist初始化松弛贪心地进行松弛操作伪代码求解单源单汇点未完 求解单源最短路的Dijkstra算法 Dijkstra算法1,英文为Dijkstra’s algorithm,常被译为迪杰斯特拉算法...

    求解单源最短路的Dijkstra算法

    Dijkstra算法1,英文为Dijkstra’s algorithm,常被译为迪杰斯特拉算法。该算法由Edsger Wybe Dijkstra2在1956年发现。Dijkstra算法使用类似BFS的方法解决带权无负权图的单源最短路问题。

    算法描述

    解决单源最短路,便是需要求解图GG上某个源点ss到其它点vV{s}v\in V- \lbrace s \rbrace的权值和最小的路径,这里显然有两个重要求解目标——权值和、路径,这里我们先不考虑具体路径的求解。

    解集dist初始化

    Dijkstra算法在过程中动态维护解集distdist,其中dist[i]dist[i]为当前ss到编号为ii的点之间的最小权值和。显然在算法开始前,有
    dist[s]=0dist[v]=dist[s]=0 \\ dist[v]=\infty

    松弛

    Dijkstra的基础操作是松弛。显然对于任意时刻,如果存在一条边w(u,v)w(u,v),使得当前dist[u]+weight[u][v]<dist[v]dist[u]+weight[u][v]<dist[v],则可利用该边,将之前的解路径path[v]path[v]优化为path[u]w(u,v)path[u]\rightarrow w(u,v)

    贪心地进行松弛操作

    算法维护两个顶点集合SSQQ。集合SS保留所有已知实际最短路径值的顶点,而集合QQ则保留其他所有顶点。集合SS初始状态为空,而后每一步都有一个顶点从QQ移动到SS。这个被选择的顶点是QQ中拥有最小的distdist值的顶点。当一个顶点uuQQ中转移到了SS中,算法对uu的每条邻边w(u,v)w(u,v)进行松弛。

    由于初始时dist[s]dist[s]00最小,故第一轮中的松弛其实是将dist[v]dist[v]初始化为weight[s][v]weight[s][v],整个算法将进行nn轮松弛。也有说法将第一轮松弛作为初始化的一部分,认为n1n-1轮松弛即可得到结果。这是亟需辨析的点。

    伪代码

    《算法导论》给出了以下伪代码:
    在这里插入图片描述

    求解单源单汇点

    上述流程中,一旦对汇点tt的松弛完成,则意味着最终的dist[t]dist[t]已经求得,此时可以终止算法。但该操作并不会降低算法的渐进复杂度,因为该汇点可能在最后一个才被选中进行松弛。
    在这里插入图片描述

    时间复杂度

    我们发现整个算法的复杂度主要由顶点数和EXTRACTMINEXTRACT-MIN决定。在朴素的Dijkstra算法中,我们很容易想到枚举distidist_i打擂找出每轮的最小值,这一操作的复杂度为O(V)O(|V|),也就是整个算法的复杂度为O(V2)O(|V|^2)

    事实上,因为我们无差别地将当前顶点集QQ首的邻点丢进QQ,所以算法实际上遍历了每一条边,因此可以更准确地将复杂度写为O(V2+E)O(|V|^2+|E|)
    但打擂也太蠢了。我们完全可以使用堆来优化EXTRACTMINEXTRACT-MIN过程,最方便的是使用STL中的priority_queue,这种情况下EXTRACTMINEXTRACT-MIN的复杂度降到了O(logV)O(\log |V|),整体复杂度为O((E+V)logV)O((|E|+|V|)\log |V|)
    如果使用斐波纳契堆实现优先队列,还可以将算法复杂度转为O(E+VlogV)O(|E|+|V|\log |V|),但当图为稠密图时,常数可能过大,并没有取得显著的效率提升。

    正确性证明

    我们考虑用数学归纳法来证明Dijkstra算法的正确性,这里仅用简单的言语描述推理过程,如有兴趣了解更多,可参见算法导论或Dijkstra本人的证明,这些内容都可以在WikiPedia3上找到。

    1. 源点入队
    2. 取队首,然后松弛,实际上也就是令disti=weight[s][i]dist_i=weight[s][i],将每次松弛产生的distdist插入队列。
    3. 取队首,此时取出的实际上就是与ss直接相连的最近的点,我们且称之为v1v_1,我们可以证明此时distv1dist_{v_1}已最小,原因是如果distv1dist_{v_1}未达最小,我们就可以通过松弛操作优化它,但松弛的前提是存在点kk使得dist[k]+weight[k][v1]<dist[v1]dist[k]+weight[k][v_1]<dist[v_1],显然,如果存在该松弛,则有dist[k]<dist[v1]dist[k]<dist[v_1],这与当前取出队首为distdist最小点矛盾。利用v1v_1松弛其邻点,同样,将更新后的distdist插入优先队列。
    4. 同3理,可推得每一步取出的队首都应该无法再被松弛,其distdist已达最小值(这也是前面说到可以优化单汇求解过程的原理)。

    参考实现

    struct HeapNode {
        int d, u;
        bool operator < (const HeapNode& rhs) const {
            return d > rhs.d;
        }
    };
    struct Dijkstra {
        int n, m;
        vector<Edge> edges;
        vector<int> G[maxn];
        bool done[maxn]; //是否已永久标号
        int d[maxn]; //s到各个点的距离
        int p[maxn]; //最短路中的上一条弧
        void init(int n) {
            this->n = n;
            for (int i = 0; i < n; i++) G[i].clear();
            edges.clear();
        }
    
        void AddEdge(int from, int to, int dist) {
            edges.push_back(Edge(from, to, dist));
            m = edges.size();
            G[from].push_back(m - 1);
        }
    
        void dijkstra(int s) {
            priority_queue<HeapNode> Q;
            for (int i = 0; i < n; i++) d[i] = INF;
            d[s] = 0;
            memset(done, 0, sizeof(done));
            Q.push((HeapNode) {0, s});
            while (!Q.empty()) {
                HeapNode x = Q.top();
                Q.pop();
                int u = x.u;
                if (done[u]) continue;
                done[u] = true;
                for (int i = 0; i < G[u].size(); i++) {
                    Edge &e = edges[G[u][i]];
                    if (d[e.to] > d[u] + e.dist) {
                        d[e.to] = d[u] + e.dist;
                        p[e.to] = G[u][i];
                        Q.push((HeapNode) {d[e.to], e.to});
                    }
                }
            }
        }
    };
    

    1. 维基百科编者. 戴克斯特拉算法[G/OL]. 维基百科, 2020(20200630)[2020-06-30]. ↩︎

    2. 维基百科编者. 艾兹赫尔·戴克斯特拉[G/OL]. 维基百科, 2019(20190823)[2019-08-23]. ↩︎

    3. 戴克斯特拉算法#時間複雜度 ↩︎

    展开全文
  • 分析:这题可以用djkstra做,但是 分别求单源最短路的话,时间复杂度比较高。 可以通过反向见图,求所有点到X的最短路。 Code(1): #include&lt;cstring&gt; #include&lt;cstdio&gt; #include&...

    题目大意:

    有向图,给定某个顶点X,问所有点到X以及从X返回原点之和最小值中的最大值是多少。

    分析:这题可以用djkstra做,但是 分别求单源最短路的话,时间复杂度比较高。

    可以通过反向见图,求所有点到X的最短路。

    Code(1):

    #include<cstring>
    #include<cstdio>
    #include<vector>
    #include<queue>
    #include<iostream>
    using namespace std;
    typedef pair<int,int> P;
    const int MAXN = 1010;
    const int INF = 0x3f3f3f3f;
    struct edge{
    	int to,w;
    	edge(){}
    	edge(int tt, int ww):to(tt),w(ww){};
    };
    vector<edge> G[MAXN];
    int d[MAXN];
    int dis[MAXN][MAXN];
    int n,m,x;
    void dijkstra(int s){
    	priority_queue<P,vector<P>,greater<P> > q;
    	fill(d,d+n+1,INF);
    	d[s] = 0;
    	q.push(P(0,s));
    	while(!q.empty()){
    		P p = q.top(); q.pop();
    		int u = p.second;
    		if(d[u] < p.first) continue; // 注意这里 
    		for(int v = 0; v < G[u].size(); ++v){
    			edge e = G[u][v];
    			if(d[e.to] > d[u] + e.w){
    				d[e.to] = d[u] + e.w;
    				q.push(P(d[e.to],e.to));
    			}
    		}
    	}
    }
    
    int main()
    	{
    		ios::sync_with_stdio(false);
    		int a,b,c;
    		while(cin >> n >> m >> x){
    			for(int i = 0; i <= n; ++i){
    				for(int j = 0; j <= n; ++j){
    					dis[i][j] = INF;
    				}
    			}
    			for(int i = 0; i < m; ++i){
    				cin >> a >> b >> c; 
    				G[a].push_back(edge(b,c));
    			}
    			for(int i = 1; i <= n; ++i){
    				dijkstra(i);
    				for(int j = 1; j <= n; ++j){
    					dis[i][j] = d[j];
    				}
    			}
    			int ans = 0;
    			for(int i = 1; i <= n; ++i){
    				ans = max(ans,dis[i][x]+dis[x][i]);
    			}
    			cout << ans << endl;
    		}
    			
    		return 0;
    	}

     

    Code(2):反向建图,前向星

    #include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<queue>
    #include<cstring>
    using namespace std;
    const int INF = 0x3f3f3f3f;
    const int N = 100100;
    int u[N],v[N],w[N],d[N]; //这里记录的是边的个数 N范围一定是边的个数 
    int res[2][N]; // 0 记录 x 到其他点 ,1记录其他点到x 
    int head[N],tol;
    int n,m,x;
    typedef pair<int,int> pii;
    
    struct Edge{
    	int u,v,w,nex;
    }e[N];
    
    void init(){
    	tol = 0;
    	memset(head,-1,sizeof(head));
    }
    
    void addEdge(int u, int v, int w){
    	e[tol].u = u; e[tol].v = v;e[tol].w = w;
    	e[tol].nex = head[u];
    	head[u] = tol++;
    }
    
    void dijkstra(int s){
    	priority_queue<pii,vector<pii>,greater<pii> > q;
    	while(!q.empty()) q.pop(); 
    	for(int i = 1; i <= n; ++i) d[i] = (i==s ? 0 : INF);
    	q.push(pii(d[s],s));
    	int u,v,w;
    	while(!q.empty()){
    		pii p = q.top(); q.pop();
    		u = p.second;
    		if(d[u] < p.first) continue;
    		for(int i = head[u]; i != -1; i = e[i].nex){
    			u = e[i].u; v = e[i].v; w = e[i].w;
    			if(d[v] > w + d[u]){
    				d[v] = w + d[u];
    				q.push(pii(d[v],v));
    			}
    		}
    	}	
    }
    
    int main()
    	{
    		ios::sync_with_stdio(false);
    		cin.tie(NULL);
    		while(cin >> n >> m >> x){
    			init();
    			for(int i = 0; i < m; ++i){
    				cin >> u[i] >> v[i] >> w[i];
    				addEdge(u[i],v[i],w[i]);
    			}
    			dijkstra(x);
    			for(int i = 1; i <= n; ++i){
    				res[0][i] = d[i];
    			}
    			init();
    			for(int i = 0; i < m; ++i){
    				addEdge(v[i],u[i],w[i]);
    			}
    			dijkstra(x);
    			for(int i = 1; i <= n; ++i) res[1][i] = d[i];
    			int ans = 0;
    			for(int i = 1; i <= n; ++i){
    				if(res[0][i] + res[1][i] < INF){
    					ans = max(res[0][i] + res[1][i],ans);
    				}
    			}
    			cout << ans << endl;
    		}
    		
    		
    		return 0;
    	}

     

    展开全文
  • 最短路之单源最短路

    千次阅读 2015-12-23 10:41:05
    在学习图论的过程中,最短论问题是比较常见且又具有代表性的一类问题。最短路是给定两个定点,在以这两个点作为起点和终点的路径中,边的权值和最小的路径。在实际生活中,最常见的最... 单源最短路问题就是将起点固

            在学习图论的过程中,最短论问题是比较常见且又具有代表性的一类问题。最短路是给定两个定点,在以这两个点作为起点和终点的路径中,边的权值和最小的路径。在实际生活中,最常见的最短路问题,就是在地图导航上应用。比如我们把权值作为距离,那么我们就可以求得A到B的最短路径。如果时间作为权值,那么我们就可以得到A到B的最短时间。

    1、Bellman-Ford算法

             单源最短路问题就是将起点固定,求该起点到其他所有点的最短路问题。贝尔曼-福特算法(Bellman-Ford)是由理查德·贝尔曼(Richard Bellman) 和 莱斯特·福特(Lester Ford) 创立的,求解单源最短路径问题的一种算法。有时候这种算法也被称为 Moore-Bellman-Ford 算法,因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行|V|-1次松弛操作,得到所有可能的最短路径。其优于Dijkstra算法的方面是边的权值可以为负数、实现简单,缺点是时间复杂度过高,高达O(VE)。但算法可以进行若干种优化,提高了效率。

    ①算法描述

            设dist[v]表示从源点s到v的最短路径长度。对于与v相邻的任意顶点u,dist[v]满足三角不等式:

                     dist[v] ≤ dist[u] + w(u, v),   (其中w(u,v)为边(u, v)的权值)

            我们设d[v]为s到v的最短路权值上界(可能为无穷大,即不连通),称为最短路估计。

            如果 d[v] > d[u] + w(u, v),即说明d[v]还可以变得更小。于是我们就使 d[v] = d[u] + w(u, v),我们称这个操作为松弛操作。 

            显然每次通过松弛操作我们都可以使得d[v]减小,直到d[v]的值不在变化(即当d[v]等于dist[v])。

    我们容易知道,在一个没有负权环的图中。每一个顶点至多与其它|V|-1个顶点进行松弛操作,若大于|V|-1,则必然存在负权环。

    对于图G(V,E),下面给出Bellman-Ford的算法流程

    输入:图G和起点S
    输出:s到每一个点的最短路径,以及图中是否存在负权环
    具体流程:
    1、初始化d数组,d[s] = 0, d[i] = ∞ (i ≠ s)
    2、枚举每一条边,进行松弛操作
    3、将操作2重复执行|V|-1次
    4、枚举每一条边,看是否能够进行松弛操作,若能,这说明原图存在负权环

    ②时间复杂度

    对于Bellman-Ford,由于每次操作需要枚举|E|条边,总共需要重复|V|-1次操作,则我们容易得出其时间复杂度为O(VE)。如果我们使用队列进行优化,则时间复杂度可下降为O(kE),k是个比较小的系数(并且在绝大多数的图中,k<=2,然而在一些精心构造的图中可能会上升到很高)。

    ③代码实现

    我们以hduXYZZY为例:

    <1>未优化版

    #include <cstdio>
    #include <cstring>
    #define INF 0xfffffff
    #define MAXN (100 + 10)
    using namespace std;
    
    struct edge{
        int from, to;
        edge(int f = 0, int t = 0)
        : from(f), to(t){}
    };
    
    edge es[MAXN*MAXN];
    int cost[MAXN];
    bool graph[MAXN][MAXN];
    int d[MAXN];
    //判断图是否联通
    void Floyd(int n){
        for(int i = 1; i <= n; i++){
            for(int k = 1; k <= n; k++){
                for(int j = 1; j <= n; j++){
                    if(!graph[i][j])
                        graph[i][j] = graph[i][k] && graph[k][j];
                }
            }
        }
    }
    
    bool bellman_ford(int s, int V, int E){
        for(int i = 0; i <= V; i++)
            d[i] = -INF;
        d[s] = 100;
        //重复对每一条边进行松弛操作
        for(int k = 0; k < V-1; k++){
            for(int i = 0; i < E; i++){
                edge e = es[i];
                //松弛操作
                if(d[e.to] < d[e.from] + cost[e.to] && d[e.from] + cost[e.to] > 0){
                    d[e.to] = d[e.from] + cost[e.to];
                }
            }
        }
        //检查负权环
        for(int i = 0; i < E; i++){
            edge e = es[i];
            if(d[e.to] < d[e.from] + cost[e.to] && graph[e.to][V] && d[e.from] + cost[e.to] > 0)
                return true;
        }
        return d[V] > 0;
    }
    
    int main(){
        int n, m, cnt, vex;
        while(scanf("%d", &n), n != -1){
            memset(graph, false, sizeof(graph));
            cnt = 0;
            for(int i = 1; i <= n; i++){
                scanf("%d%d", &cost[i], &m);
                for(int j = 0; j < m; j++){
                    scanf("%d", &vex);
                    es[cnt++] = edge(i, vex);
                    graph[i][vex] = true;
                }
            }
            Floyd(n);
            if(!graph[1][n] || !bellman_ford(1, n, cnt)){
                printf("hopeless\n");
            }
            else{
                printf("winnable\n");
            }
        }
        return 0;
    }
    

    <2>队列优化SPFA

    单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm。 SPFA算法是西南交通大学段凡丁于1994年发表的。松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上,用一个队列记录松弛过的节点,可以避免了冗余计算。我们还是以hdu1317xyzzy为例,代码如下:

    #include <cstdio>
    #include <cstring>
    #include <queue>
    #define MAXN (100 + 10)
    using namespace std;
    //d表示s到各点的所经过路径的权值之和
    //cost表示各点的权值
    //cnt表示进入队列的次数
    int d[MAXN], cost[MAXN], cnt[MAXN];
    //reach表示两点之间是否联通,即可达
    //graph记录两点之间是否有边
    bool reach[MAXN][MAXN], graph[MAXN][MAXN];
    
    
    void Init(){
        memset(d, 0, sizeof(d));
        memset(cnt, 0, sizeof(cnt));
        memset(graph, false, sizeof(graph));
        memset(reach, false, sizeof(reach));
    }
    
    //判断图是否联通
    void Floyd(int n){
        for(int i = 1; i <= n; i++){
            for(int k = 1; k <= n; k++){
                for(int j = 1; j <= n; j++){
                    if(!reach[i][j])
                        reach[i][j] = reach[i][k] && reach[k][j];
                }
            }
        }
    }
    
    bool SPFA(int s, int n){
        queue<int> Q;
        d[s] = 100;
        Q.push(s);
        while(!Q.empty()){
            int now = Q.front();
            Q.pop();
            cnt[now]++;
            //如果不存在负权环(PS:在本题中为正权环),即每个点进入队列的次数至多为n-1
            //若大于n-1,即表明必然存在负权环
            if(cnt[now] >= n) return reach[now][n];
            //依次枚举每条边
            for(int next = 1; next <= n; next++){
                if(graph[now][next] && d[now] + cost[next] > d[next] && d[now] + cost[next] > 0){
                    Q.push(next);
                    d[next] = d[now] + cost[next];
                }
            }
        }
        return d[n] > 0;
    }
    
    int main(){
        int n, m, vex;
        while(scanf("%d", &n), n != -1){
            Init();
            for(int i = 1; i <= n; i++){
                scanf("%d%d", &cost[i], &m);
                for(int j = 0; j < m; j++){
                    scanf("%d", &vex);
                    reach[i][vex] = true;
                    graph[i][vex] = true;
                }
            }
            Floyd(n);
            if(!reach[1][n] || !SPFA(1, n)){
                printf("hopeless\n");
            }
            else{
                printf("winnable\n");
            }
        }
        return 0;
    }
    


    2、Dijkstra算法

    我们容易发现,如果图中没有负边的情况。在Bellman-Ford算法中,如果d[u]还不是最短距离的话,那么即便我们进行了松弛操作,那么d[v]也不会变为最短距离。而且即便d[v]没有变化,那么他还是需要检查一次所有的边。显然这些操作很浪费时间,于是乎,我们就提出了以下改进:

    (1)从最短距离已经确定的顶点出发更新与之相邻顶点的最短距离。

    (2)对于最短距离已经确定的顶点,我们直接无视。

    通过这样的修改我们就得到了Dijkstra算法。Dijkstra算法是用来解决只含非负权值边的图的单源最短路问题。换而言之,Dijkstra无法处理含有负权边的图。

    ①算法描述

    对于图G(V,E),下面给出Dijkstra的算法流程

    输入:图G和起点S
    输出:s到每一个点的最短路径
    具体流程:
    1、初始化d数组,d[s] = 0, d[i] = ∞ (i ≠ s)
    2、设置所有点未访问过(即设置一个标记数组,并将其置空)
    3、找出所有未访问过的点中距离值最小的点,将其标记为访问过
    4、对3中找到的点的相邻边进行松弛操作
    5、重复3和4直到所有点都访问过

    下边给出一幅图来模拟Dijkstra的过程:



    ②时间复杂度

    因为操作更新|V|次,每次操作需要找最小值,扫描一个点连接的所有边,如果我们使用堆来实现寻找和维护,则时间复杂度为O( (|E|+|V|) log|V| )。若只用普通的方法扫描,时间复杂度为O(|V|² + |E|)。

    ③代码实现

    我们以hdu 1874畅通工程续 来说明Dijkstra算法:

    <1>未优化版

    #include <cstdio>
    #include <vector>
    #include <algorithm>
    #define MAXN 200 + 10
    #define INF 0xffffff
    using namespace std;
    struct Vex{
        int v, weight;
        Vex(int tv, int tw):v(tv), weight(tw){}
    };
    //graph用来记录图的信息
    vector<Vex> graph[MAXN];
    //判断是否已经找到最短路
    bool inTree[MAXN];
    //源点s到各顶点最短路的值
    int mindist[MAXN];
    //初始化
    void Init(int n){
        for(int i = 0; i < n; i++){
            inTree[i] = false;
            graph[i].clear();
            mindist[i] = INF;
        }
    }
    //s表示源点,t表示终点,n表示顶点数目
    int Dijkstra(int s, int t, int n){
        int tempMin, tempVex, addNode;
        //初始化s
        mindist[s] = 0;
        //将源点s标记为访问过
        inTree[s] = true;
        //题目中可能有重边,我们去除重边
        for(unsigned int i = 0; i < graph[s].size(); i++)
            mindist[graph[s][i].v] = min(mindist[graph[s][i].v], graph[s][i].weight);
        //从剩下的n-1个点逐个枚举
        for(int nNode = 1; nNode <= n-1; nNode++){
            tempMin = INF;
            //寻找所有未访问过点中,有最小距离的点
            for(int i = 0; i < n; i++){
                if(!inTree[i] && mindist[i] < tempMin){
                    tempMin = mindist[i];
                    addNode = i;
                }
            }
            //将该点标记为访问过
            inTree[addNode] = true;
            //将与该点相邻的点进行松弛操作
            for(unsigned int i = 0; i < graph[addNode].size(); i++){
                tempVex = graph[addNode][i].v;
                if(!inTree[tempVex] && tempMin + graph[addNode][i].weight < mindist[tempVex]){
                    mindist[tempVex] = tempMin + graph[addNode][i].weight;
                }
            }
        }
        return mindist[t];
    }
    
    
    int main(){
        int n, m;
        int v1, v2, x, s, t;
        while(scanf("%d%d", &n, &m) != EOF){
            Init(n);
            for(int i = 0; i < m; i++){
                scanf("%d%d%d", &v1, &v2, &x);
                graph[v1].push_back(Vex(v2, x));
                graph[v2].push_back(Vex(v1, x));
            }
            scanf("%d%d", &s, &t);
            int ans = Dijkstra(s, t, n);
            if(ans == INF)
                printf("-1\n");
            else
                printf("%d\n", ans);
        }
        return 0;
    }

    <2>堆优化版

    #include <cstdio>
    #include <vector>
    #include <queue>
    #include <algorithm>
    #define MAXN 200 + 10
    #define INF 0xffffff
    using namespace std;
    struct edge{
        int to, cost;
    };
    typedef pair<int, int> P;
    vector<edge> graph[MAXN];
    int mindist[MAXN];
    
    void Init(int n){
        for(int i = 0; i < n; i++){
            graph[i].clear();
            mindist[i] = INF;
        }
    }
    
    int Dijkstra_heap(int s, int t, int n){
        //pair的first存放s->v的距离
        //second存放顶点v
        priority_queue<P, vector<P>, greater<P> > Q;
        //初始化源点s的信息
        mindist[s] = 0;
        Q.push(P(0, s));
        while(!Q.empty()){
            //每次从堆中取出最小值
            P p = Q.top(); Q.pop();
            int v = p.second;
            //当取出的值不是当前最短距离的话,就丢弃这个值
            if(mindist[v] < p.first) continue;
            //将与其相邻的点,进行松弛操作
            for(unsigned int i = 0; i < graph[v].size(); i++){
                edge e = graph[v][i];
                if(mindist[e.to] > mindist[v] + e.cost){
                    mindist[e.to] = mindist[v] + e.cost;
                    //将满足条件的点重新加入堆中
                    Q.push(P(mindist[e.to], e.to));
                }
            }
        }
        return mindist[t];
    }
    
    
    int main()
    {
        int n, m;
        int v1, v2, x, s, t;
        while(scanf("%d%d", &n, &m) != EOF){
            Init(n);
            for(int i = 0; i < m; i++){
                scanf("%d%d%d", &v1, &v2, &x);
                graph[v1].push_back({v2, x});
                graph[v2].push_back({v1, x});
            }
            scanf("%d%d", &s, &t);
            int ans = Dijkstra_heap(s, t, n);
            if(ans == INF)
                printf("-1\n");
            else
                printf("%d\n", ans);
        }
        return 0;
    }
    




    PS:如果不懂优先队列的,请移步:传送门

    PPS:在附赠一个大礼包,图论500题

    展开全文
  • SPFA单源最短路算法

    2019-04-09 20:18:29
    SPFA单源最短路算法 适用情况 与 Dijkstra 算法类似,只不过该算法可以判断是否存在负环(不能处理负环)。目的是求单源最短路。 时间复杂度为 O(nm) 该算法可由 Dijkstra 算法替换使用,优于其在于可判断负环...
  • 题目描述 如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。 输入输出格式 输入格式: 第一行包含三个整数N、M、S,分别表示点的个数、有向边的个数、出发点的编号。 接下来M行每行包含三个整数...
  • Dijkstra单源最短路算法 适用情况 该算法适用于边权为非负的情况,且最好为稀疏图。目的是求单源最短路。 时间复杂度O() 有向图、无向图可初始化 map 数组时进行处理。 思想 该算法采用贪心的策略。 ①...
  • Dijkstra算法-单源最短路
  • 但是因为解决单源最短路问题的复杂度也是一样的, 因此通常当作单源最短路问题来求解。 分析: 记从起点s出发到顶点的最短距离为dp[i]。则下述等式成立。 dp[i]=min {dp[i]+(从j到i的边的权值)|e=(j,)∈E} : 如果...
  • [Acwing提高]单源最短路的建图方式 知识点 题目 扩展方式 类型 热浪 裸的单源最短路 SPFA/dijkstra 题目 热浪 SPFA代码 在这里插入代码片
  • SPFA算法是解决最短路问题的算法 今天来回顾一下单源最短路的问题: 利用SPFA算法可以高效的解决单源最短路问题,并且解决有无负环的问题 如该无向图所示: 假设我们的单源点是1 Part: 我们从1 ...
  • 一看这不是明显的单源最短路么呵呵。。。于是直接上来来了个dijkstra,而且用的是邻接表存储图—— Submit之后,结果却是—— 我立刻被雷到了QAQ。。。于是立刻改写spfa,结果—— 4000...
  • 算法笔记——图论(1)单源最短路 定义 最短路: 给定两个顶点,以这两个顶点为起点和终点的所有路径中,边的权值和最小的路径。 单源最短路:固定一个起点,求它到其他所有点的最短路的距离。 若终点也固定,...
  • Dijkstra算法是单源最短路算法,可以求解不带负权边的图中,从源点s到其它所有点的最短路。 时间复杂度近似O(n^2),可以用堆优化。 一般用邻接表,也可用邻接矩阵。在稠密图上会有较好的性能表现。 在这里插入代码片...
  • 单源最短路 DijkstraDijkstraDijkstra O(n2)O(n^2)O(n2) 堆优化版的DijkstraDijkstraDijkstra O(mlogn)O(mlogn)O(mlogn) SPFASPFASPFA O(m)O(m)O(m) 最坏O(nm)O(nm)O(nm) 多源最短路 FloydFloydFloyd O(n3)O(n^3)O...
  • 单源最短路的模板,链式前向星写法。 非负权的单源最短路Dijkstra算法。 Dijkstra #include<bits/stdc++.h> using namespace std; const int INF=0x3f3f3f3f; /* begin 链式前向星 */ const int MAXN=...
  • spfa(求单源最短路

    2019-05-02 16:26:03
    单源最短路:给定一个带权值的有向图,给定图中的一个定点V,则V称为源,V能到达所有的顶点的最短距离称为单源最短路 二、图的存储方式 #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define M ...
  • 图论--单源最短路

    2021-02-04 16:25:33
    # 图论--单源最短路dijkstra(优先队列优化)spfa(bfs版)spfa(dfs版,没听说过吧)bellman-ford 因为以前太懒,所以前没发什么博客。今天本人第一天写博客吧,hh 因为本人擅长图论就从图论开始吧。 说到图论,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,634
精华内容 1,453
关键字:

单源最短路