dijkstra算法（输出最短路径）

89 阅读 0 评论 59 点赞

我是靠谱客的博主眼睛大歌曲，这篇文章主要介绍dijkstra算法（输出最短路径），现在分享给大家，希望可以做个参考。

题目描述
给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

输入描述:
输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)
输出描述:
输出一行有两个数，最短距离及其花费。
示例1

输入
3 2
1 2 5 6
2 3 4 5
1 3
0 0
输出
9 11
————————————————

复制代码

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
/* 图的信息 */
typedef struct Edge {
int s;
int e;
int l;
int c;
Edge(int s, int e, int l, int c) {
this->s = s;
this->e = e;
this->l = l;
this->c = c;
}
void print() {
printf("start:%d end:%d length:%d cost:%d n",this->s,this->e,this->l,this->c);
}
} Edge;
vector<Edge> graph[1001];
typedef struct Point {
int num; // 点的编号
int distanceFromStart; // 从源点的距离
bool operator < (const Point& a) const {
return
distanceFromStart > a.distanceFromStart;
}
Point(int n, int d) {
this->num = n;
this->distanceFromStart = d;
}
} Point;
int n, m; // 1 ~ n 编号 ； m个边
int u, v; // 起点 终点
int INF = 9999999;
int dis[1001];
int cost[1001];
void print() {
cout << "graph" << endl;
for (int i = 1; i <= n; i ++) {
cout << "index:" << i << endl;
for (int j = 0; j <= graph[i].size() - 1; j++) {
graph[i][j].print();
}
}
}
void dijkstra(int u) {
priority_queue<Point> q;
dis[u] = 0;
cost[u] = 0;
q.push(Point(u,0));
while(!q.empty()) {
int father = q.top().num;
//
cout << "father:" << father << endl;
q.pop();
for (int i = 0; i <= graph[father].size() - 1; i++) {
int s = graph[father][i].s;
int e = graph[father][i].e;
int l = graph[father][i].l;
int c = graph[father][i].c;
if (dis[e] > dis[s] + l || (dis[e] == dis[s] + l && cost[e] > cost[s] + c)) {
dis[e] = dis[s] + l;
cost[e] = cost[s] + c;
q.push(Point(e,dis[e]));
}
}
}
return ;
}
int main() {
while (cin >> n >> m && n != 0 && m != 0) {
// 初始化
for (int i = 1; i <= n; i++) {
graph[i].clear();
}
for (int i = 1; i <= n; i ++) {
dis[i] = INF;
cost[i] = 0;
}
// 输入
int s,e,l,c;
for (int i = 1; i <= m; i++) {
cin >> s >> e >> l >> c;
//
cout << s << e << l << c << endl;
graph[s].push_back(Edge(s, e, l, c));
graph[e].push_back(Edge(e, s, l, c));
}
//
print(); // 测试了 没问题
//填充dis cost
cin >> u >> v;
dijkstra(u);
cout << dis[v] << " " <<
cost[v] << endl;
}
}
```c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
/* 图的信息 */
typedef struct Edge {
int s;
int e;
int l;
int c;
Edge(int s, int e, int l, int c) {
this->s = s;
this->e = e;
this->l = l;
this->c = c;
}
void print() {
printf("start:%d end:%d length:%d cost:%d n",this->s,this->e,this->l,this->c);
}
} Edge;
vector<Edge> graph[1001];
typedef struct Point {
int num; // 点的编号
int distanceFromStart; // 从源点的距离
bool operator < (const Point& a) const {
return
distanceFromStart > a.distanceFromStart;
}
Point(int n, int d) {
this->num = n;
this->distanceFromStart = d;
}
} Point;
int n, m; // 1 ~ n 编号 ； m个边
int u, v; // 起点 终点
int INF = 9999999;
int dis[1001];
int cost[1001];
void print() {
cout << "graph" << endl;
for (int i = 1; i <= n; i ++) {
cout << "index:" << i << endl;
for (int j = 0; j <= graph[i].size() - 1; j++) {
graph[i][j].print();
}
}
}
void dijkstra(int u) {
priority_queue<Point> q;
dis[u] = 0;
cost[u] = 0;
q.push(Point(u,0));
while(!q.empty()) {
int father = q.top().num;
//
cout << "father:" << father << endl;
q.pop();
for (int i = 0; i <= graph[father].size() - 1; i++) {
int s = graph[father][i].s;
int e = graph[father][i].e;
int l = graph[father][i].l;
int c = graph[father][i].c;
if (dis[e] > dis[s] + l || (dis[e] == dis[s] + l && cost[e] > cost[s] + c)) {
dis[e] = dis[s] + l;
cost[e] = cost[s] + c;
q.push(Point(e,dis[e]));
}
}
}
return ;
}
int main() {
while (cin >> n >> m && n != 0 && m != 0) {
// 初始化
for (int i = 1; i <= n; i++) {
graph[i].clear();
}
for (int i = 1; i <= n; i ++) {
dis[i] = INF;
cost[i] = 0;
}
// 输入
int s,e,l,c;
for (int i = 1; i <= m; i++) {
cin >> s >> e >> l >> c;
//
cout << s << e << l << c << endl;
graph[s].push_back(Edge(s, e, l, c));
graph[e].push_back(Edge(e, s, l, c));
}
//
print(); // 测试了 没问题
//填充dis cost
cin >> u >> v;
dijkstra(u);
cout << dis[v] << " " <<
cost[v] << endl;
}
}
```c