Dijkstra朴素版

NoGift

2023-08-18 18:36:12

发布于：河北

0阅读

0回复

0点赞

朴素 dijkstra 算法 ——求最短路

时间复杂是 O(n^2+m), n 表示点数，m 表示边数

n 1000， m 1e6

邻接矩阵存储

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

邻接表存储

#include<bits/stdc++.h>
using namespace std;

const int N = 3000;
struct node{
	int to, w; // 去点，边权 
};
int n, m;  
vector<node> g[N]; //存图 
int dis[N]; //最短距离数组 
bool vis[N]; 
int sx, ex; // 起点，终点 
void dijkstra(){
	// 1.初始化 
	memset(dis, 0x3f, sizeof dis);
	dis[sx] = 0;
//	vis[sx] = true;
	// 2. 循环
	for(int i=0; i<n-1; i++){
		int t = -1;// 找距离最小 
		for(int j = 1; j <= n; j++){
			if(!vis[j] && (t == -1 || dis[j] < dis[t])){
				t = j;
			}
		}
		vis[t] = true; 
		for(auto node : g[t]){
			int next = node.to;
			if(vis[next]) continue;
			// 3. 松弛  relax 更新 
			if(dis[t]  + node.w < dis[next]){
				dis[next] = dis[t]  + node.w;
			}
		}
	} 
}
int main(){
	cin>>n>>m>>sx>>ex;
	for(int i=0; i<m; i++){
		int a, b, w;
		cin>>a>>b>>w;
		g[a].push_back({b, w});
		g[b].push_back({a, w});
	}
	dijkstra();
	cout << dis[ex] << endl;

	return 0;
}