const int MAXN = 205; const int INF = 999999; int n; int maps[MAXN][MAXN]; bool visited[MAXN]; int pre[MAXN]; int dist[MAXN]; void init() { memset(visited, false, sizeof(visited)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if(i == j) { maps[i][j] = 0; } else { maps[i][j] = INF; } } pre[i] = i; dist[i] = INF; } } void Dijkstra(int s, int e) //起点,终点 { int i, j; int minValue, minNode; dist[s] = 0; visited[s] = true; for (i = 1; i <= n; i++) { dist[i] = maps[s][i]; if(dist[i] == INF) { pre[i] = 0; } else { pre[i] = s; } } for (i = 1; i <= n; i++) { minValue = INF; minNode = 0; for (j = 1; j <= n; j++) { if(!visited[j] && minValue > dist[j]) { minNode = j; minValue = dist[j]; } } if(minNode == 0) { break; } visited[minNode] = true; for (j = 1; j <= n; j++) { if(!visited[j] && maps[minNode][j] != INF && dist[j] > dist[minNode] + maps[minNode][j]) { dist[j] = dist[minNode] + maps[minNode][j]; pre[j] = minNode; } } if(minNode == e) { break; } } }
Dijkstra模版
Keep it simple!