图结构练习——最短路径（Dijkstra算法）

迷南。 2022-07-10 15:58 209阅读 0赞

字节跳动校招内推码: C4BDSMC
    投递链接: https://job.toutiao.com/s/J691fRK
    内推交流QQ群：1049175720

think:  
1注意重复边的覆盖  
2注意map数组的初始化  
3注意dist数组的初始化

[sdut原题链接][sdut]

图结构练习——最短路径  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
给定一个带权无向图，求节点1到节点n的最短路径。

Input  
输入包含多组数据，格式如下。  
第一行包括两个整数n m，代表节点个数和边的个数。(n<=100)  
剩下m行每行3个正整数a b c，代表节点a和节点b之间有一条边，权值为c。

Output  
每组输出占一行，仅输出从1到n的最短路径权值。（保证最短路径存在）

Example Input  
3 2  
1 2 1  
1 3 1  
1 0

Example Output  
1  
0

Hint

Author  
赵利强

以下为accepted代码

#include <iostream>
    #include <stdio.h>
    #include <string.h>
    
    using namespace std;
    
    #define INF  0x3f3f3f3f
    int n, m;
    int map[104][104], vis[104], dist[104];
    
    void Dijkstra(int v)
    {
    	int i, j, k;
    	for(i = 1; i <= n; i++)//dist数组的初始化
    	{
    		dist[i] = map[v][i];
    		vis[i] = 0;
    	}
    	dist[v] = 0;
    	vis[v] = 1;
    
    	for(i = 0; i < n-1; i++)
    	{
    		int min = INF, u = v;
    		for(j = 1; j <= n; j++)//寻找未标记结点的最小值
    		{
    			if(vis[j] == 0 && dist[j] < min)
    			{
    				u = j;
    				min = dist[j];
    			}
    		}
    		vis[u] = 1;
    
    		for(k = 1; k <= n; k++)//更新最短路
    		{
    			if(vis[k] == 0 && map[u][k] < INF && dist[k] > dist[u] + map[u][k])
    			{
    				dist[k] = dist[u] + map[u][k];
    			}
    		}
    	}
    }
    int main()
    {
    	int i, j, a, b, c;
    	while(scanf("%d %d", &n, &m) != EOF)
    	{
    		memset(vis, 0, sizeof(vis));
    		for(i = 1; i <= n; i++)
    		{
    			for(j = 1; j <= n; j++)
    			{
    				if(i == j)
    					map[i][j] = 0;
    				else
    					map[i][j] = INF;
    			}
    		}
    		for(i = 0; i < m; i++)
    		{
    			scanf("%d %d %d", &a, &b, &c);
    			if(map[a][b] > c)///避免覆盖最短路
    				map[a][b] = map[b][a] = c;
    		}
    		if(m == 0)
                printf("0\n");
            else
            {
                Dijkstra(1);
                printf("%d\n", dist[n]);
            }
    
    	}
    	return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 12ms
    Take Memory: 208KB
    Submit time: 2017-02-17 19:30:41
    ****************************************************/

以下为wrong answer代码——Dijkstra算法理解不扎实，导致变量位置使用错误（将u的位置写成了v）

#include <iostream>
    #include <stdio.h>
    #include <string.h>
    
    using namespace std;
    
    #define INF  0x3f3f3f3f
    int n, m;
    int map[104][104], vis[104], dist[104];
    
    void Dijkstra(int v)
    {
    	int i, j, k;
    	for(i = 1; i <= n; i++)//dist数组的初始化
    	{
    		dist[i] = map[v][i];
    		vis[i] = 0;
    	}
    	dist[v] = 0;
    	vis[v] = 1;
    
    	for(i = 0; i < n-1; i++)
    	{
    		int min = INF, u = v;
    		for(j = 1; j <= n; j++)//寻找未标记结点的最小值
    		{
    			if(vis[j] == 0 && dist[j] < min)
    			{
    				u = j;
    				min = dist[j];
    			}
    		}
    		vis[u] = 1;
    
    		for(k = 1; k <= n; k++)//更新最短路
    		{
    			if(vis[k] == 0 && map[v][k] < INF && dist[k] > dist[u] + map[u][v])
    			{
    				dist[k] = dist[u] + map[u][k];
    			}
    		}
    	}
    }
    int main()
    {
    	int i, j, a, b, c;
    	while(scanf("%d %d", &n, &m) != EOF)
    	{
    		memset(vis, 0, sizeof(vis));
    		for(i = 1; i <= n; i++)
    		{
    			for(j = 1; j <= n; j++)
    			{
    				if(i == j)
    					map[i][j] = 0;
    				else
    					map[i][j] = INF;
    			}
    		}
    		for(i = 0; i < m; i++)
    		{
    			scanf("%d %d %d", &a, &b, &c);
    			if(map[a][b] > c)///避免覆盖最短路
    				map[a][b] = map[b][a] = c;
    		}
    		if(m == 0)
                printf("0\n");
            else
            {
                Dijkstra(1);
                printf("%d\n", dist[n]);
            }
    
    	}
    	return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Wrong Answer
    Take time: 16ms
    Take Memory: 208KB
    Submit time: 2017-02-17 19:27:15
    ****************************************************/

以下为wrong answer代码——  
1 没有考虑到重复边的覆盖问题  
2 map数组初始化错误

#include <stdio.h>
    #include <string.h>
    #define INF 9999999
    int n, m;
    int map[104][104], dist[10400], vis[10400];
    void Dijkstra(int v)
    {
    	for(int i = 1; i <= n; i++)
    	{
    		dist[i] = map[v][i];
    		vis[i] = 0;
    	}
    	vis[v] = 1;
    	dist[v] = 0;
    	for(int i = 0; i < n-1; i++)
    	{
    		int min = INF, u = v;
    		for(int j = 1; j <= n; j++)//寻找未访问的结点中的最小值
    		{
    			if(vis[j] == 0 && dist[j] < min)
    			{
    				u = j;
    				min =dist[j];
    			}
    		}
    		vis[u] = 1;
    
    		for(int k = 1; k <= n; k++)//更新
    		{
    			if(vis[k] == 0 && map[u][k] < INF && dist[k] > dist[u] + map[u][k])
    			{
    				dist[k] = dist[u] + map[u][k];
    			}
    		}
    	}
    }
    int main()
    {
    	int a, b, c;
    	while(scanf("%d %d", &n, &m) != EOF)
    	{
    		memset(map, 0, sizeof(map));
    		memset(vis, 0, sizeof(vis));
    		for(int i = 0; i < m; i++)
    		{
    			scanf("%d %d %d", &a, &b, &c);
    			map[a][b] = c;
    		}
    		Dijkstra(1);
    		printf("%d\n", dist[n]);
    	}
    	return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Wrong Answer
    Take time: 12ms
    Take Memory: 192KB
    Submit time: 2017-02-17 18:41:44
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2013/pid/2143