单源最短路径问题–Dijkstra

首先，Dijkstra算法解决的是单源最短路问题，即给定图G(V,E)和起点s（起点又称为源点），求起点s到达其他顶点的最短距离。

注意
Dijkstra算法只能应对所有边权都是非负数的情况，如果边权出现负数，那么迪杰斯特拉算法很可能会出错，这时最好使用SPFA算法。

Dijkstra算法的策略是：
设置集合S存放已被访问的顶点（即已攻占的城市），然后执行n次下面的两个步骤（n为顶点个数）；
1.每次从集合V-S（即未攻占的城市）中选择与起点s的最短距离最小的一个顶点（记为u），访问并加入集合S的（即令其已被攻占）。
2.之后，令顶点u为中介点，优化起点s与所有从u能到达的顶点v之间的最短距离。

Dijkstra算法的具体实现：

迪杰斯特拉算法的策略比较偏重于理论化。
1.集合S可以用一个bool 型数组  vis[]来实现 ，即当vis[i]==true 时表示顶点Vi已被访问，当vis[i]==false 时表示顶点Vi未被访问。
2.令int型数组 d[]表示起点s到达顶点Vi的最短距离，初始时除了起点s的d[s]赋为0，其余顶点都赋为一个很大的数
（初学者可以用1000000000，就是10^9，或者用0x3fffffff）来表示INF，就是不可达。

//Dijkstra 算法伪代码 模板


//G 为图，一般设为全局变量；数组d为源点到达各点的
//最短路径长度，s为起点



Dijkstra(G,d[],s) 
{
    初始化;

    for(循环n次) 
    {
        u=使d[u]最小的还未被访问的顶点的标号;

        记u已被访问;

        for(从u出发能到达的所有顶点v) 
        {

            if(v未被访问  && 以u为中介点使s到顶点v的最短距离d[v]更优)
            {
                优化d[v]; 

            }


        }



    } 




}



//Dijkstra 具体程序实现模板

//最大顶点数 
const int MAXV =1000;
//定义无穷大

const int INF=0x3fffffff;


//邻接矩阵版
//使用于点数不大（例如V不超过1000）的情况，相对好写

int n,G[MAXV][MAXV];
//起点到达各点的最短路径长度
int d[MAXV];
//标记数组，vis[i]==true 表示已被访问
bool vis[MAXV]={
  false};


//s为起点 
void Dijkstra(int s) 
{
    //fill函数将整个d数组赋为INF(慎用memset) 
    fill(d,d+MAXV，INF);

    //起点s到达自身的距离为0 
    d[s]=0; 


    //循环顶点数，就是n次 
    for(int i=0;i<n;i++)
    {
        //u使d[u]最小，MIN存放最小的d[u] 

        int u=-1;
        int MIN=INF;

        //找到未访问的顶点中d[]最小的 
        for(int j=0;j<n;j++)
        {
            if(vis[j]==false && d[j]<MIN  )
            {
                u=j;
                MIN=d[j];

            }


        }

        //找不到小于INF的d[u],说明剩下的顶点和起点s不连通

        if(u==-1)
         {
            return;
         }


        //标记u为已被访问 
        vis[u]=true;

        for(int v=0;v<n;v++)
        {
            //如果v未被访问 && u能到达v && 以u为中介点可以使d[v]更优

            if( vis[v]==false && G[u][v]!=INF  && d[u]+G[u][v]<d[v]  )
             {
                //优化d[v] 
                d[v]=d[u]+G[u][v];

             }



        }





    }







}




//邻接表版


struct Node{

    //v为边的目标顶点，dis为边权 

    int v,dis;

};


//图G，adj[u] 存放从顶点u出发可以到达的所有顶点 
vector<Node> adj[MAXV];

//n为顶点数，图G使用邻接表实现，MAXV为最大顶点数 
int n; 
//起点到达各点的最短路径长度 
int d[MAXV];
//标记数组，vis[i]==true 表示已被访问。初值均为false

bool vis[MAXV]={
  false};

//s为起点 
void Dijkstra(int s) 
{
    fill(d,d+MAXV，INF);

    d[s]=0;

    for(int i=0;i<n;i++)
    {
        int u=-1;
        int MIN=INF;

        for(int j=0;j<n;j++)
        {

            if(vis[j] == false && d[j]<MIN )
            {
                u=j;
                MIN=d[j]; 

            }


        }


        //找不到小于INF的d[u],说明剩下的顶点和起点s不连通
        if(u==-1) 
        {
            return;

        }

        //标记u已被访问 
        vis[u]=true;

        //只有下面这个for循环与邻接矩阵的写法不同

        for(int j=0;j<adj[u].size();j++) 
        {
            //通过邻接表直接获得u能到达的顶点v 
            int v=adj[u][j].v;
            if( vis[v]==false && d[u]+adj[u][j].dis<d[v] ) 
            {
                //如果v未被访问&&以u为中介点可以使d[v]更优

                 //优化d[v] 
                d[v]=d[u]+adj[u][j].dis;

            }


        }






    }






}