使用邻接矩阵的时间复杂度为O(n^2),用优先队列的复杂度为O(mlogn)

(一)  过程

每次选择一个未访问过的到已经访问过（标记为Known）的所有点的集合的最短边，并用这个点进行更新，过程如下：

Dv为最短路，而Pv为前面的顶点。

1.     初始

2.     在v1被标记为已知后的表

3.     下一步选取v4并且标记为known，顶点v3,v5,v6,v7是邻接的顶点，而他们实际上都需要调整。如表所示:

4.     接下来选取v2,v4是邻接点，但已经是known的，不需要调整，v5是邻接的点但不做调整，因为经过v2的值为2+10=12而长为3的路径已经是已知的。

5.     接下来选取v5，值为3，v7 3+6>5不需调整，然后选取v3，对v6的距离下调到3+5=8

6.     再选下一个顶点是v7，v6变为5+1=6

7.     最后选取v6

(二)  局限性

Dijkstra没办法解决负边权的最短路径，如图

运行完该算法后，从顶点1到顶点3的最短路径为1,3，其长度为1，而实际上最短路径为1,2,3，其长度为0.（因为过程中先选择v3，v3被标记为已知，今后不再更新）

(三) 算法实现。

1．普通的邻接表 以（HDU 1874 畅通工程续 SPFA || dijkstra）为例

用vis作为上面标记的known，dis记录最短距离（记得初始化为一个很大的数）。

void dijkstra(int s)
{
	memset(vis,0,sizeof(vis));       
	int cur=s;                   
	dis[cur]=0;
	vis[cur]=1;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)                     
			if(!vis[j] && dis[cur] + map[cur][j] < dis[j])   //未被标记且比已知的短，可更新
				dis[j]=dis[cur] + map[cur][j] ;

		int mini=INF;
		for(int j=0;j<n;j++)                  
			if(!vis[j] && dis[j] < mini)    //选择下一次到已知顶点最短的点。
				mini=dis[cur=j];
		vis[cur]=true;
	}	
}

要重载个比较函数。

struct point  
{  
    int val,id;  
    point(int id,int val):id(id),val(val){}  
    bool operator <(const point &x)const{  
        return val>x.val;  
    }  
};  
void dijkstra(int s)  
{  
    memset(vis,0,sizeof(vis));  
    for(int i=0;i<n;i++)  
        dis[i]=INF;   
  
    priority_queue<point> q;  
    q.push(point(s,0));  
    vis[s]=true;  
    dis[s]=0;  
    while(!q.empty())  
    {  
        int cur=q.top().id;  
        q.pop();  
        vis[cur]=true;  
        for(int i=head[cur];i!=-1;i=e[i].next)  
        {  
            int id=e[i].to;  
            if(!vis[id] && dis[cur]+e[i].val < dis[id])  
            {  
                dis[id]=dis[cur]+e[i].val;  
                q.push(point(id,dis[id]));  
            }  
        }         
    }  
}  

void SPFA(int s)  
{  
    for(int i=0;i<n;i++)  
        dis[i]=INF;  
  
    bool vis[MAXN]={0};  
      
    vis[s]=true;  
    dis[s]=0;  
      
    queue<int> q;  
    q.push(s);  
    while(!q.empty())  
    {  
        int cur=q.front();  
        q.pop();  
        vis[cur]=false;  
        for(int i=0;i<n;i++)  
        {  
            if(dis[cur] + map[cur][i] < dis[i])  
            {  
                dis[i]=dis[cur] + map[cur][i];  
                if(!vis[i])  
                {  
                    q.push(i);  
                    vis[i]=true;  
                }  
            }             
        }  
    }  
}  

void spfa(int s)
{
	memset(vis,0,sizeof(vis));
	for(int i=0;i<n;i++)
		dis[i]=INF;	

	queue<int> q;
	q.push(s);
	vis[s]=true;
	dis[s]=0;
	while(!q.empty())
	{
		int cur=q.front();
		q.pop();
		vis[cur]=false;
		for(int i=head[cur];i!=-1;i=e[i].next)
		{
			int id=e[i].to;
			if(dis[id] > dis[cur]+e[i].val)
			{
				dis[id] = dis[cur] + e[i].val;
				if(!vis[id])
				{
					vis[id]=true;
					q.push(id);
				}
			}
		}
	}
}

bool spfa()  
{  
    for(int i=0;i<=n;i++)  
        dis[i]=INF;  
  
    bool vis[MAXN]={0};  
    int cnt[MAXN]={0};  
    queue<int> q;  
    dis[0]=0;  
    vis[0]=true;  
    cnt[0]=1;  
    q.push(0);  
  
    while(!q.empty())  
    {  
        int cur=q.front();  
        q.pop();  
        vis[cur]=false;  
  
        for(int i=head[cur];i!=-1;i=e[i].next)  
        {  
            int id=e[i].to;  
            if(dis[cur] + e[i].val > dis[id])  
            {  
                dis[id]=dis[cur]+e[i].val;  
                if(!vis[id])  
                {  
                    cnt[id]++;  
                    if(cnt[cur] > n)  
                        return false;  
                    vis[id]=true;  
                    q.push(id);  
                }  
            }  
        }  
    }  
    return true;  
} 

（三）：优化

void floyd()
{
    for(int k=0;k<n;k++)
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}