算法分析——单源最短路径问题

╰+哭是因爲堅強的太久メ 2023-02-17 02:19 48阅读 0赞

1、问题描述

> 给定图G（V，E），求一条从起点到终点的路径，使得这条路径上经过的所有边的边权之和最小

2、Dijkstra算法  
      迪杰斯特拉算法用来解决单源最短路问题，即给定图G和起点V，通过算法得到V到达其它顶点的最短距离。  
      其基本思想是：设置顶点集合S，并不断地做贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。  
      初始时，S中仅含有源。设u是G的某一个顶点，把源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。  
      Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist做必要的修改。  
      一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。  
      Dijkstra算法的伪代码：

// n为顶点数，v为源点，数组c为源点到达各个顶点的最短路径
    void Dijkstra(int n, int v, int c[][N]) { 
    	初始化
    	for(n-1次循环) { 
    		for(n次循环) { 
    			取出最短路径的顶点
    		}
    		for(n次循环) { 
    			更新Dist值
    		}
    	}
    }

3、代码实现

void Dijkstra(int n, int v, int c[][N])  
    {   
        bool s[N];	
        int dist[N] = { 0},prev[N] = { 0};
    	int i, j;
    	// 初始化邻接矩阵
        for(i=1; i<=n; i++) {   
            dist[i] = c[v][i];//dist[i]表示当前从源到顶点i的最短特殊路径长度 
            s[i] = false;  
            if(dist[i] == M)  prev[i] = 0;//记录从源到顶点i的最短路径i的前一个顶点 
            else  prev[i] = v;  
        }  
    
        dist[v] = 0;  
        s[v] = true;    
        for(i=1; i<n; i++) {  // n-1次循环做贪心选择 
            int temp = M;  
            int u = v;//上一顶点 
            //取出V-S中具有最短特殊路径长度的顶点u 
            for(j=1; j<=n; j++) {   
            	// 当前状态做一次贪心选择
                if((!s[j]) && (dist[j]<temp)) {   // 打擂台，取出最小值
                    u = j;  
                    temp = dist[j];  
                }  
            }  
            s[u] = true;  
            //根据作出的贪心选择更新Dist值 
            for(j=1; j<=n; j++) {   
                if((!s[j]) && (c[u][j]<M)) {   
                    int newdist = dist[u] + c[u][j];  
                    if(newdist < dist[j]) {   // 如果该路径更短
                        dist[j] = newdist;  // 更新路径
                        prev[j] = u;  // 记录前一个顶点
                    }  
                }  
            }  
        }  
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTEwOTg1_size_16_color_FFFFFF_t_70]

4、结果截图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTEwOTg1_size_16_color_FFFFFF_t_70 1]  
参考文献  
\[1\] 王晓东. 计算机算法设计与分析\[M\].5版. 北京：电子工业出版社，2018.  
\[2\] 胡凡，曾磊. 算法笔记\[M\]. 北京：机械工业出版社，2019.

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTEwOTg1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200610200325764.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTEwOTg1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTEwOTg1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200610200045369.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTEwOTg1,size_16,color_FFFFFF,t_70