基础算法题——单源最短路（Dijkstra-迪杰斯特拉）

心已赠人 2022-12-19 15:27 179阅读 0赞

#### Dijkstra-迪杰斯特拉 ####

处理单源最短路径问题常用的算法  
推荐：[Dijkstra详解][Dijkstra]  
类似的算法 [Floyd 弗洛伊德][Floyd]，效率上并没有Dijkstra-迪杰斯特拉高

--------------------

#### [单源最短路][Link 1] ####

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

#### 题目中如何实现 Dijkstra？ ####

**工具：邻接表 + 标记表 + 城市与 s 最短路径表**

**思路：在最优的条件下，枚举寻找下一个最优的条件（排除已经是最优的城市）。**  
由于每次循环都只能为一个城市找到最佳路径，所以必须重复进行 n-1 次循环（城市数量 n）。

#include<bits/stdc++.h>
    using namespace std;
    int len[2600][2600];
    int dis[2600], n;
    bool bj[2600] = { false};
    const int Max = 1e9+7;
    
    void init(){ 
    	for(int i=1; i<2600; i++)
    	for(int j=1; j<2600; j++){ 
    		if(i==j)
    			len[i][j]=0;
    		else
    			len[i][j]=Max;
    	}
    	return;
    }
    
    void Dijkstra(int s){ 
    	bj[s] = true;
    	for(int i=1; i<n; i++){ 
    		int u, Min = Max;
    		
    		//寻找当前最优且没被走过的路径 
    		for(int j=1; j<=n; j++)
    		if(dis[j]<Min&&!bj[j]){ 
    			Min = dis[j];
    			u = j;
    		}
    		
    		//在最优的路径下找下一个可能最优的路径 
    		bj[u] = true;
    		for(int j=1; j<=n; j++)
    		if(dis[j]>dis[u]+len[u][j])
    			dis[j] = dis[u]+len[u][j];
    	}
    	
    	return;
    }
    
    int main(){ 
    	int m, s, t;
    	init();
    	scanf("%d%d%d%d", &n, &m, &s, &t);
    	while(m--){ 
    		int x, y, z;
    		scanf("%d%d%d", &x, &y, &z);
    		if(len[x][y]>z){ 
    			len[x][y]=z;
    			len[y][x]=z;
    		}
    	}
    	for(int i=1; i<=n; i++)
    		dis[i] = len[s][i];
    	Dijkstra(s);
    	printf("%d", dis[t]);
    	return 0;
    }

[Dijkstra]: https://blog.csdn.net/qq_35644234/article/details/60870719?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160484477819725255526789%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=160484477819725255526789&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-1-60870719.pc_first_rank_v2_rank_v28p&utm_term=Dijkstra&spm=1018.2118.3001.4449
[Floyd]: https://blog.csdn.net/Zhengyangxinn/article/details/104613216
[Link 1]: https://loj.ac/problem/119
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/9e039d4ebbd84383a3c4e52e8d95de22.png
[timu]: /images/20221120/c1360b199da0452f9d6f2b6365929484.png