最短路1： dijkstra算法

单源最短路（从一个点 到 其他各个点的距离）：

使用条件：当所有边权都是正数的时候 （一定不能存在负权边，有负权边就一定不能适用dijkstra算法）

稠密图：使用朴素dijkstra算法：

时间复杂度为：O(n * n); //n为点个数

稀疏图：堆优化dijkstra算法：

时间复杂度为:0(mlogn) //m为边数，n为点的个数

使用dijkstra算法：

(1)当为稠密图的时候：使用朴素版的dijkstra算法更优。

时间复杂度为：O(n * n);   //n为点个数


(2)当为稀疏图的时候，使用堆优化版的dijkstra算法更优。

时间复杂度为:0(mlogn) //m为边数，n为点的个数

dijkstra算法的思路

循环n次。

每循环一次找到一个当前结点到  源点距离最短的点。并且这个点不在集合T中（此集合T 用于存放已经确定的距离最短的点）
然后将这个找到的当前结点存入到集合中（可以使用一个数组choose[i] = 1来表示在集合中）

然后用这个存入集合的结点t去修改其他结点j（与他相连的点）到源点的距离。
dist[j] = min(dist[j] , dist[t] + g[t][j] );

而堆优化优化思路：

堆优化  主要是对  每循环一次找到一个当前结点到  源点距离最短的点。 这个操作进行优化。

使用小根堆：  queue<pair<int,int> , vector< pair<int,int > > , greater< pair<int,int> > >;

使用堆优化的时候有一个坏处，就是使用priority_queue<>的时候不允许修改，  所以就需要冗余。


所以
auto temp = q.top();
q.pop();

int dist = q.first; //存距离
int t = q.second; //存结点

if(choose[t] == 1)  //这个就是因为可能会有冗余，t 已经是存入到集合中被确定的点了。所以可以直接continue;
{
    continue;    
}
choose[t] = 1;

朴素版dij算法的实现：

int dij()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    for(int i = 1 ; i < n ; i++)
    {
        int t = -1;
        for(int j = 1 ; j <= n ; j++)
        {
            if(!choose[j] && (t == -1 || dist[t] > dist[j]))
            {
                t = j;
            }
        }

        choose[t] = 1;

        for(int j = 1 ; j <= n ; j++)
        {
            dist[j] = min(dist[j] , dist[t] + g[t][j]);
        }
    }
    if(dist[n] == 0x3f3f3f3f)
    {
        return -1;
    }
    else
    {
        return dist[n];
    }
}

堆优化的dij()算法:

typedef pair<int,int> PII;
priority_queue<PII,vector<PII> , greater<PII>> q;

int dij()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    q.push({0,1});
    while(q.size())
    {
        auto temp = q.top();
        q.pop();
        int dis = temp.first;
        int loc = temp.second;
        if(choose[loc] == 1)
        {
            continue;
        }
        choose[loc] = 1;
        for(int i = h[loc] ; i != -1 ; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dis + w[i])
            {
                dist[j] = dis + w[i];
                q.push({dist[j] , j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f)
    {
        return -1;
    }
    else
    {
        return dist[n];
    }
}