本文主要是介绍Dijkstra——Travel Plan，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
解法1： Dijkstra
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;const int MAXV = 1010;
const int INF = 1000000000;
int n, m, st, ed, G[MAXV][MAXV], cost[MAXV][MAXV];
int d[MAXV], c[MAXV], pre[MAXV];
bool vis[MAXV] = {false};
vector<int> t;void Dijkstra(int s)
{fill(d, d + MAXV, INF);fill(c, c + MAXV, INF);d[s] = 0;c[s] = 0;for(int i = 0; i < n; i++){ // 循环 n 次int u = -1, MIN = INF;for(int j = 0; j < n; j++){if(vis[j] == false && d[j] < MIN){u = j;MIN = d[j];} } // 找最小if(u == -1) return;vis[u] = true; // 拉入 for(int v = 0; v < n; v++){if(vis[v] == false && G[u][v] != INF){if(d[u] + G[u][v] < d[v]){d[v] = d[u] + G[u][v];c[v] = c[u] + cost[u][v];pre[v] = u;} else if(d[u] + G[u][v] == d[v]){if(c[u] + cost[u][v] < c[v]){c[v] = c[u] + cost[u][v];pre[v] = u;}}}} // 更新 }
} void Print(int ed)
{t.push_back(ed);int x = ed;while(x != st){x = pre[x];t.push_back(x);}for(int i = t.size() - 1; i >= 0; i--){printf("%d ",t[i]);}printf("%d %d\n", d[ed], c[ed]);
}int main()
{fill(G[0], G[0] + MAXV * MAXV, INF);fill(cost[0], cost[0] + MAXV * MAXV, INF);scanf("%d%d%d%d", &n, &m, &st, &ed);int c1, c2, dis, cos;for(int i = 0; i < m; i++){scanf("%d%d%d%d", &c1, &c2, &dis, &cos);G[c1][c2] = dis;G[c2][c1] = dis;cost[c1][c2] = cos;cost[c2][c1] = cos;}Dijkstra(st);Print(ed);return 0;
}/*
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
*/
解法2： Dijkstra + DFS
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXV = 510;
const int INF = 1000000000;int n, m, st, ed, G[MAXV][MAXV], cost[MAXV][MAXV];
int d[MAXV], minCost = INF;
bool vis[MAXV] = {false};
vector<int> pre[MAXV];
vector<int> tempPath, path;void Dijkstra(int s)
{fill(d, d + MAXV, INF);d[s] = 0;for(int i = 0; i < n; i++){ // 循环 n 次 int u = -1, MIN = INF;for(int j = 0; j < n; j++){if(vis[j] == false && d[j] < MIN){u = j;MIN = d[j];}}if(u == -1) return;vis[u] = true;for(int v = 0; v < n; v++){if(vis[v] == false && G[u][v] != INF){if(d[u] + G[u][v] < d[v]){d[v] = d[u] + G[u][v];pre[v].clear();pre[v].push_back(u); } else if(d[u] + G[u][v] == d[v]){pre[v].push_back(u); }}} // 更新 }
}void DFS(int v)
{if(v == st){ // 递归到叶子节点tempPath.push_back(v);int tempCost = 0;for(int i = tempPath.size() - 1; i > 0; i--){ // 计算耗费 int id = tempPath[i], idNext = tempPath[i - 1];tempCost += cost[id][idNext]; } if(tempCost < minCost){minCost = tempCost;path = tempPath;} // 更新最优路径tempPath.pop_back();return; }tempPath.push_back(v);for(int i = 0; i < pre[v].size(); i++){DFS(pre[v][i]); } tempPath.pop_back();
}int main()
{fill(G[0], G[0] + MAXV * MAXV, INF);fill(cost[0], cost[0] + MAXV * MAXV, INF);scanf("%d%d%d%d", &n, &m, &st, &ed);int c1, c2, dis, cos;for(int i = 0; i < m; i++){scanf("%d%d%d%d", &c1, &c2, &dis, &cos);G[c1][c2] = dis;G[c2][c1] = dis;cost[c1][c2] = cos;cost[c2][c1] = cos;}Dijkstra(st);DFS(ed);for(int i = path.size() - 1; i >= 0; i--){printf("%d ", path[i]);}printf("%d %d\n", d[ed], minCost);return 0;
}
这篇关于Dijkstra——Travel Plan的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
