最短路径算法

最短路径算法可以分为两类：单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径。多源最短路径问题：求任意两顶点间的最短路径。对于无权图，其最短路径算法可以使用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算法的实现，题目本身并不难。但是，我在写的过程中，犯了两个错误。第一个是，我开始使用的是优先队列，后来发现不行，因为无法更新插入到队列中的值。会导致取出来的不是最小的一个。第二个是，在构建图的时候，忘了是无向图，没有插入。后来出现了运行时的错误才发现。