Dijkstra从入门到出门

发布于 2018-09-09  326 次阅读


Dijkstra算法是一种求最短路的算法。

朴素的Dijkstra时间复杂度 O(n²)

此算法不适用于 边权为负 的图

不啰嗦了,开门见

我在后门看你十分钟了!!!

dijkstra可以求两点间的最短路径,这种也叫单源最短路。

而Floyd求的是多个点之间的最短路。

dijkstra有很多奇奇怪怪的优化,我们后面用STL优先级队列(priority_queue)把dijkstra优化到O(nlogn)

朴素的Dijkstra

思想&&实现

dijkstra的思想大体是这样: 找与当前点距离最小的点,同时用它来更新与他相邻的其它点。

我们,有一张无向图。

求2到4的最短路径。

我们开一个dis数组和vis数组,dis[i]=j表示起点到i号点的距离为j,vis[i]表示i号结点有没有被遍历过。

初始化:

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        e[i][j] = 99999999;

先把dis[i]设为原点到点i的距离,这样才方便求min~~

for (int i = 1; i <= n; i++)
    dis[i] = e[1][i];

我们先从2号点开始遍历,我们把vis[2]设为true,把dis[2]设为0(因为2是原点)。

vis[start] = true;
dis[start] = 0;

这是原点,所以不需要其他操作(更新最短路)

我们枚举2号结点的临边

我们的循环首先找到了5,5没有被遍历.

我们用5推出其他节点的路径:dis[6] < dis[5]+27=29,发现比他长,不改. dis[1]=dis[5]+8=10,

Dijkstra的形式类似于广搜,而不是深搜

我们接着寻找2号结点的其他临边,找到了点6,vis[6]=true.

用6更新5号,1号点,发现比他们大,不更新。

for (int i = 1; i <= n; i++)
{   
    u = 0;
    min = 99999999;
    for (int j = 1; j <= n; j++)
        if (vis[j] == false && min > dis[j])
        {
            dis[j] = min;
            u = j;
        }

    if (u)
    {
        vis[u] = true;
        for (int v = 1; v <= n; v++)
            if (dis[v] > dis[u] + e[u][v])
                dis[v] = dis[u] + e[u][v];
    }
}

至此,2到每个点的路经为:

dis[] = {10, 0, 9999999, 9999999, 2, 5}

后面的处理相信你也会了,本弱不多说了。。。

代码实现


#include <iostream>

using namespace std;

int m, n, e[10000][10000], dis[10000], a, b, q, start, u;
bool vis[10000] = {};

int main()
{
    cin >> n >> m;
    cin >> start;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            e[i][j] = 99999999;

    for (int i = 1; i <= m; i++)
    {
        cin >> a >> b >> q;
        e[a][b] = q;
        e[b][a] = q;
        e[a][a] = 0;
        e[b][b] = 0;
    }

    for (int i = 1; i <= n; i++)
        dis[i] = e[start][i];
    /*----------核心代码----------*/
    dis[start] = 0;
    vis[start] = true;
    for (int i = 1; i <= n; i++)
    {
        u = 0;
        int Min = 99999999;
        for (int j = 1; j <= n; j++)
            if (vis[j] == false && Min > dis[j])
            {
                Min = dis[j];
                u = j;
            }

        if (u)
        {
            vis[u] = true;
            for (int v = 1; v <= n; v++)
                if (dis[v] > dis[u] + e[u][v])
                    dis[v] = dis[u] + e[u][v];
        }
    }
    /*-----------------------------*/
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";
    return 0;
}

STL堆(优先级队列)优化的Dijkstra

对之前的思考

我们在找最短路时,有这么一段代码:

for (int j = 1; j <= n; j++)
    if (vis[j] == false && Min > dis[j])
    {
        Min = dis[j];
        u = j;
    }

这段代码可以优化

它的作用是找一个与当前节点距离最小的点,我们用的是的是顺序查找,复杂度为O(n),而我们学过的堆正好可以找最小值,时间复杂度为O(logn),再乘上我们的另一个n,于是复杂度变为O(nlogn)。

代码实现

#include <cstdio>
#include <queue>

#define maxn 1000000

using namespace std;

/*----------邻接表----------*/

int head[maxn], num = 0;
struct node
{
    int data;
    int to;
    int next;
} edge[maxn];

inline void add_edge(int from, int to, int data)
{
    edge[++num].next = head[from];
    head[from] = num;
    edge[num].data = data;
    edge[num].to = to;
}

/*----------优先级队列----------*/

struct Heap         //小根堆
{
    int d, e;           //到e权值为d
    bool operator<(const Heap &b) const  //运算符重载
    {
        return d > b.d;
    }
};

priority_queue<Heap> q;

/*----------Dijkstra----------*/

int n, m, dis[maxn] = {}, start;
bool vis[maxn] = {};

inline void Dijkstra(int start)
{
    Heap x;
    q.push((Heap) {0, start});      //定义临时对象
    dis[start] = 0;

    while (!q.empty())
    {
        x = q.top();        //找一个与当前节点距离最小的点
        q.pop();
        int e = x.e;

        if (vis[e]) 
            continue;

        vis[e] = true;
        for (int i = head[e]; i; i = edge[i].next)      //用找到的点更新最短路并加入堆
        {
            dis[edge[i].to] = min(dis[edge[i].to], dis[e] + edge[i].data);  
            q.push((Heap){dis[edge[i].to], edge[i].to});
        }
    }
}

/*----------主函数----------*/

int main(int argc, char **argv)
{
    scanf("%d%d%d", &n, &m, &start);
    for (int i = 1; i <= m; i++)
    {
        int q, w, e;
        scanf("%d%d%d", &q, &w, &e);
        add_edge(q, w, e);
    }

    for (int i = 1; i <= n; i++)     //初始化
        dis[i] = 2147483647;

    Dijkstra(start);

    for (int i = 1; i <= n; i++)
        printf("%d ", dis[i]);
    return 0;
}