最短路径算法可以分为两类：单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径。多源最短路径问题：求任意两顶点间的最短路径。对于无权图，其最短路径算法可以使用BFS，这里就不再介绍了。
对于单源有权的最短路径问题，有一个很出名的算法：Dijkstra算法。它所使用的是贪心算法，它的过程和BFS类似，只是做了一些改进。首先，在取元素的时候，它是按照最小值去取的，而BFS是直接按照加入的顺序。其次，加入元素，都需要去更新这些元素的值。下面给出它的伪代码描述：
/* 不能解决有负边的情况 */
void Dijkstra( Vertex s ){
while (1) {
V = 未收录顶点中dist最小者;
if ( 这样的V不存在 ){
break;
}
collected[V] = true;
for ( V 的每个邻接点 W ){
if ( collected[W] == false ){
if ( dist[V]+E<V,W> < dist[W] ) {
dist[W] = dist[V] + E<V,W> ;
path[W] = V;
}
}
}
}
}
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。输入格式:输入数据的第1行给出4个正整数其中
是城市的个数，顺便假设城市的编号为
；M是高速公路的条数；
是出发地的城市编号；D是目的地的城市编号。随后的
行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。输出格式:在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。
输入样例:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
输出样例:
3 40
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#define MAX 1000000
typedef struct edge Edge;
typedef struct count Count;
typedef vector<Edge> Vertex;
typedef vector<Edge>::iterator Iterator;
struct edge {
int s;//起点
int d;//目的地
int l;//长度
int m;//花费，钱
edge(int s,int d,int l,int m):s(s),d(d),l(l),m(m) {}
edge():s(-1),d(-1),l(MAX),m(MAX) {}
};
struct count {
int l;//长度
int m;//花费
int d;//目的地
count(int d,int l,int m):d(d),l(l),m(m) {}
count():d(-1),l(MAX),m(MAX) {}
};
bool operator<(Count c1,Count c2) {
if(c1.l < c2.l) {
return true;
} else if(c1.l == c2.l) {
if(c1.m < c2.m) {
return true;
} else {
return false;
}
} else {
return false;
}
}
int main() {
int N,M,S,D;
cin>>N>>M>>S>>D;
Count result[N];//结果
Vertex vertex[N];//地图
int visited[N];//记录是否走过
memset(visited,0,sizeof(visited));
Iterator iterator;//迭代器
for(int i=0; i<M; i++) {
int s,d,l,m;
cin>>s>>d>>l>>m;
vertex[s].push_back(Edge(s,d,l,m));
vertex[d].push_back(Edge(d,s,l,m));
}
//使用Dijkstra算法计算最短路径
result[S] = Count(S,0,0);
//只要没有遍历完
for(int k=0;k<N;k++) {
Count c;
//找一个最小的
for(int i=0; i<N; i++) {
if(visited[i] == 0&&result[i] < c) {
c = result[i];
}
}
int d = c.d;
visited[d] = 1;//已经遍历了
//更新和它相邻的结点
for(iterator = vertex[d].begin(); iterator !=
vertex[d].end(); iterator++) {
int d = (*iterator).d;
int l = (*iterator).l;
int m = (*iterator).m;
Count c1(d,c.l + l,c.m + m);
if(c1 < result[d]) {
result[d] = c1;
}
}
}
cout<<result[D].l<<" "<<result[D].m<<endl;
return 0;
}
这个其实就是写一个Dijstra算法的实现，题目本身并不难。但是，我在写的过程中，犯了两个错误。第一个是，我开始使用的是优先队列，后来发现不行，因为无法更新插入到队列中的值。会导致取出来的不是最小的一个。第二个是，在构建图的时候，忘了是无向图，没有插入。后来出现了运行时的错误才发现。
