Dijkstra+ 链式前向星+ 优先队列

 

Dijkstra算法   

　　Dijkstra最短路算法，个人理解其本质就是一种广度优先搜索。先将所有点的最短距离Dis[ ]都刷新成∞(涂成黑色)，然后从起点x (Dis[x]= 0, Dis[]值最小 )开始查询；先将x 加入(涂成灰色)，对x 的所有边进行遍历，对所有搜索到的点x+ 1 进行松弛(刷新)，若经过x 点的松弛，得到的距离小于原来的值：Dis[x]+ dis(x, x+ 1) < Dis[x+ 1]， 则用新值刷新，把x+ 1加入(涂成灰色)；当x 的所有边都完毕，邻接的点都松弛完毕后，把x 退出(涂成白色)，继续从下一个Dis[ ]最小的点开始；重复上述步骤，直到所有的点都涂成白色，退出。

链式前向星  

　　这个不说了，之前的帖子里说过，拉到最下面就是。

 

堆优化

　　利用优先队列，对数据结构感兴趣的可以去看一下堆，这里就不说了，会用优先队列就行。

 

最短路计算：Dijkstra+ 链式前向星+ 优先队列  

　　下面进入正题。

　　还是拆分代码和用例题来解释。

①链式前向星建图  

 

using namespace std;const int MAX_E= 2000010;const int MAX_V= 200010;const int inf= 0x3f3f3f3f;struct ENode{    int to;       //终点;    int w;        //权;    int type;     //路的类型;    int next;     //下一条路的地址;};ENode Edegs[MAX_E];int Head[MAX_V]; //点Vi的第一条边的地址;int Dis[MAX_V];  //点Vi到起点的最短距离;

 

int main(){    int n, m, s;    cin >> n >> m >> s;    int t, a, b, w;    memset(Head, -1, sizeof(Head));    for (int i= 0; i< m; i ++)    {        cin >>a >>b >>w;        Edegs[i].to= b;        Edegs[i].w= w;        Edegs[i].next= Head[a];        Head[a]= i;////        有向图建图多加一次边,m 变成m* 2;//        ++ i;//        Edegs[i].to= a;//        Edegs[i].w= w;//        Edegs[i].next= Head[b];//        Head[b]= i;    }    return 0;}

 

②Dijkstra+ 优先队列

int Head[MAX_V]; //点Vi的第一条边的地址;int Dis[MAX_V];  //点Vi到起点的最短距离;struct cmpx{    //优先队列的排序函数;    bool operator()(int &a,int &b)const    {        return Dis[a]> Dis[b];    }};void Dijkstra(int x){    //用优先队列寻找Dis[]最小点;    //代替遍历搜索，节约时间;    priority_queue
     
      
       ,cmpx > q;       memset(Dis, inf, sizeof(Dis));   //染成黑色;    Dis[x]= 0;    q.push(x);                       //将x 加入队列，涂成灰色;    while (! q.empty())    {        int u= q.top();        q.pop();                     //将x 出队列，涂成白色;        for (int k= Head[u]; k!= -1; k= Edegs[k].next )        {            int v= Edegs[k].to;            if (Dis[v]> Dis[u]+ Edegs[k].w )            {                Dis[v]= Dis[u]+ Edegs[k].w;                q.push(v);           //将x+ 1加入队列，涂成灰色;            }        }    }}
      
     

 

下面是洛谷上一道最短路入门题，验证一下正确性：

 

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int MAX_E= 2000010;const int MAX_V= 200010;const int inf= 0x3f3f3f3f;struct ENode{ int to; //终点; int w; //权; int type; //路的类型; int next; //下一条路的地址;};ENode Edegs[MAX_E];int Head[MAX_V]; //点Vi的第一条边的地址;int Dis[MAX_V]; //点Vi到起点的最短距离;struct cmpx{ //优先队列的排序函数; bool operator()(int &a,int &b)const { return Dis[a]> Dis[b]; }};inline int read(){ //快速读入; int X= 0,w= 1; char ch= 0; while(ch<'0' || ch>'9') { if(ch=='-') w= -1; ch= getchar(); } while(ch>= '0' && ch<= '9') X= (X<< 3)+(X<< 1)+(ch-'0'),ch=getchar(); return X* w;}void Dijkstra(int x){ //用优先队列寻找Dis[]最小点; //代替遍历搜索，节约时间; priority_queue
            
             
              ,cmpx > q; memset(Dis, inf, sizeof(Dis)); //染成黑色; Dis[x]= 0; q.push(x); //将x 加入队列，涂成灰色; while (! q.empty()) { int u= q.top(); q.pop(); //将x 出队列，涂成白色; for (int k= Head[u]; k!= -1; k= Edegs[k].next ) { int v= Edegs[k].to; if (Dis[v]> Dis[u]+ Edegs[k].w ) { Dis[v]= Dis[u]+ Edegs[k].w; q.push(v); //将x+ 1加入队列，涂成灰色; } } }}int main(){ int n, m, s; cin >> n >> m >> s; int t, a, b, w; memset(Head, -1, sizeof(Head)); for (int i= 0; i< m; i ++) { cin >>a >>b >>w; Edegs[i].to= b; Edegs[i].w= w; Edegs[i].next= Head[a]; Head[a]= i;//// 有向图建图多加一次边,m 变成m* 2;// ++ i;// Edegs[i].to= a;// Edegs[i].w= w;// Edegs[i].next= Head[b];// Head[b]= i; } Dijkstra(s); for (int i = 1; i <= n; i ++) { if (i!= 1) printf(" "); if (Dis[i]== inf) { printf("2147483647"); } else { printf("%d", Dis[i]); } } printf("\n"); return 0;}
             
            
           
          
         
        
       
      

 

 

谢谢观看这篇随笔！