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

2019-11-08 03:08:04

字体：大中小

来源：转载

供稿：网友

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

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 0x3f3f3f3fint 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: AcceptedTake time: 12msTake Memory: 208KBSubmit 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 0x3f3f3f3fint 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 AnswerTake time: 16msTake Memory: 208KBSubmit time: 2017-02-17 19:27:15****************************************************/

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

#include <stdio.h>#include <string.h>#define INF 9999999int 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 AnswerTake time: 12msTake Memory: 192KBSubmit time: 2017-02-17 18:41:44****************************************************/

上一篇：八皇后问题（N皇后问题）

下一篇：1001. A+B Format