WHCSRL 技术网

最短路径问题|Dijkstra|Bellman-Ford/SPFA|A*拓展|C++

Dijkstra算法(单源最短路径,无负权边)

1.算法步骤

2.举例

在这里插入图片描述

在这里插入图片描述

3.代码

3.1优先队列

STL优先队列

class DijkElem{
public:
    int vertex,distance;
    DijkElem(){vertex=-1;distance=-1;}
    DijkElem(int v,int d){vertex=v;distance=d;}
    friend bool operator<(DijkElem& d1,DijkElem& d2){
        if(d1.distance==d2.distance)
            return d1.vertex<d2.vertex;
        else
            return d1.distance<d2.distance;
    }
};

//Dijkstra's shortest paths algorithm with priority queue 
void Dijkstra(Graph* G,int* D,int s){
    int v;
    DijkElem temp = DijkElem(s,0);
    int pre[G->n()];
    pre[s]=-1;
    priority_queue<DijkElem> H;
    for(int i=0;i<G->n();i++){
        D[i]=INFINITY;
        pre[i]=-2;//-2:unreachable
    }
    for(int i=0;i<G->n();i++){
        do{
            if(H.size()==0)
                return;
            DijkElem temp=H.top();
            v=temp.vertex;
            H.pop();
        }while(G->getMark(v)==VISITED);
        G->setMark(v,VISITED);
        if(D[temp.vertex]==INFINITY)//unreachable
            return;
        for(int w=G->first(v);w<G->n();w=G->next(v,w)){
            if(D[w]>D[v]+G->weight(v,w)){
                D[w]=D[v]+G->weight(v,w);
                pre[w]=v;
                H.push(DijkElem(w,D[w]));
        }
    }
}
  • 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

4.证明

5.分析

时间复杂度: O ( ( E + V ) l o g V ) O((E+V)logV) O((E+V)logV)

Bellman-Ford算法(单源最短路径,有负权边)

1.算法步骤

边-更新->点
执行|V|-1次,对每一条边进行操作

2.举例

3.代码

4.证明

5.分析

时间复杂度: O ( E V ) O(EV) O(EV)

Floyid算法(多源最短路径)

A*补充延申

推荐阅读