最短路之Dijkstra算法

时间：2021-02-05 23:23:38

1. 邻接矩阵

 int cost[MAX_V][MAX_V]; //assume cost[u][v]>0

 int d[MAX_V];

 bool used[MAX_V];

 void Dijkstra(int s, int t, int V){

     for(int i=; i<=V; i++)

         used[i]=false, d[i]=INT_MAX, pre[i]=;

     d[s]=;

     while(true){

         int u=-;

         for(int v=; v<=V; v++){

             if(!used[v]&&(u==-||d[v]<d[u])) u=v;

         }

         if(u==-||u==t) break;

         used[u]=true;

         for(int v=; v<=V; v++){

             if(!cost[u][v]||used[v]) continue;

             if(d[v]>d[u]+cost[u][v])

                 d[v]=d[u]+cost[u][v], pre[v]=u;

         }

     }

 }

2.邻接表

 #define X first

 #define Y second

 typedef pair<int, int> pii;

 typedef vector<pii> vpii;

 vpii G[MAX_V];

 int d[MAX_V];

 bool used[MAX_V];

 void Dijkstra(int s, int t, int V){

     for(int i=; i<=V; i++)

         used[i]=false, d[i]=INT_MAX, pre[i]=;

     d[s]=;

     while(true){

         int u=-;

         for(int v=; v<=V; v++){

             if(!used[v]&&(u==-||d[v]<d[u])) u=v;

         }

         if(u==-||u==t) break;

         used[u]=true;

         for(int i=; i<G[u].size(); i++){

             int &v=G[u][i].X, &c=G[u][i].Y;

             if(used[v]) continue;

             if(d[v]>d[u]+c)

                 d[v]=d[u]+c, pre[v]=u;

         }

     }

 }

相关文章