dijk

.....................用矩阵存.....................
 1 int mp[N][N];

 bool p[N];

 int dist[N];

 void dijk(int s , int n)

 {

     int i , j , k ;

     for( i =  ; i <= n ;i++)

     {

         p[i] = false;

         dist[i] = mp[s][i];

     }

     p[s] = true;

     dist[s] = ;

     for(i =  ; i < n ; i++)

     {

         int Min = INF;

         int k =  ;

         for( j =  ; j <= n ;j++)

         {

             if(!p[j]&&dist[j]<Min)

             {

                 Min = dist[j];

                 k = j;

             }

         }

         if(Min==INF) return ;

         p[k] = true;

         for(j =  ; j <= n ;j++)

         {

             if(!p[j]&&mp[k][j]!=INF&&dist[j]>dist[k]+mp[k][j])

                 dist[j] = dist[k]+mp[k][j];

         }

     }

 }

..............用链表存.................
 1 struct Edge{

     int to;

     int v ;

     int next;

 }edge[M];

 int Enct;

 int head[N];

 void add(int from ,int to , int v )

 {

     edge[Enct].to = to ;

     edge[Enct].v = v ;

     edge[Enct].next = head[from];

     head[from] = Enct++;

     edge[Enct].to = from ;

     edge[Enct].v = v ;

     edge[Enct].next = head[to];

     head[to] = Enct++;

 }

 void init ()

 {

     Enct = ;

     memset(head,-, sizeof(head));

 }

 int dist[N];

 bool p[N];

 void dijk(int s, int n)

 {

     int i , j , k ;

     for( i =  ;  i <= n ; i++ )

     {

         p[i] = false;

         dist[i]= INF;

     }

     p[s] = true;

     dist[s] = ;

     for( i = head[s] ; i != - ; i = edge[i].next)

     {

         Edge e = edge[i];

         if(e.v<dist[e.to])//考虑重边

         dist[e.to] = e.v;

     }

     for( i =  ;i < n ;i++)

     {

         int Min = INF;

         int k =  ;

         for( j =  ; j <= n ; j++)

         {

             if(!p[j]&&dist[j]<Min)

             {

                 Min = dist[j];

                 k = j;

             }

         }

         p[k] = true;

         if(Min == INF) return ;

         for( j = head[k] ;j!=- ;j=edge[j].next)

         {

             Edge e = edge[j];

             if(!p[e.to]&&dist[e.to]>dist[k]+e.v)

             {

                 dist[e.to] = dist[k]+e.v;

             }

         }

     }

 }

dijk算法思路

贪心的思想，需要一个vis数组标记这个点是否被加入过队列中，一个dis 数组，储存当前值到起始点的当前最短距离，开始所有点的dis都标记成INF，第一个点的dis 标记成0 ，扫描n次，每次都找出未加入队列的点中距离起始点最近的一个点，标记为访问过，用这个点去更新与其相连的点的到 初始点的距离，这个算法不能求负权图，不能判环。