Dijkstra算法 | lostfly's blog

文章目录

1. 介绍
2. 算法描述
1. 2.1. 邻接矩阵的图
2. 2.2. 邻接表的图
3. 优化

介绍

本算法是由Dijkstra提出的单源最短路径算法。

这种算法可以应用在有向和无向图之中，边的权重必须非负。

算法描述

邻接矩阵的图

我们先用邻接矩阵表示的图来表达问题，这样比较直观。

我们有一个邻接矩阵m标识了图里的连接情况：

m[i][j]标识了点i到点j的距离.

我们有顶点集合V，出发点S，目标点E，计算过程中并不会涉及到E，算法会遍历所有的顶点。

初始化一个dist数组，标识出发点S到所有点的距离。

dist[i] = m[s][i];

图的顶点集合V被分成两类，一类是访问过的，一类是未访问过的，访问过的点集合初始状态下只有出发点S。

每次算法都在未访问的顶点集合中寻找一个点u加入访问过的集合。
这个待定顶点必须是离出发点S最近的点，即dist[i]最小的点。
将新加入的顶点u加入访问集合，遍历所有，更新dist数组，如果找到
dist[u] + m[u][i] < dist[i] 就更新dist[i]。

将所有的顶点都加入访问列表以后，整个图就处理完了，所有dist[i]都是S到i的最短距离了。

下面是C++的实现代码：

void dijkstra(vector<vector<int>>& board, int start, int end)
{
    int N = board.size();
    vector<bool> used(N, false);
    vector<int> dist(N);
    if (start == end || board[start][end] == 0)
    {
        cout << 0 << endl;
        continue;
    }
    used[start] = 1;
    for (int i = 0; i < N; i++)
    {
        dist[i] = board[start][i];
    }
    while (true)
    {
        int min_dist = INT_MAX;
        int u = start;
        for (int i = 0; i < N; i++)
        {
            if (!used[i] && dist[i] < min_dist)
            {
                min_dist = dist[i];
                u = i;
            }
        }
        if (u == start)	//没找到min_dist，说明已经没有需要处理的点了
            break;
        used[u] = true;
        //更新dist数组
        for (int i = 0; i < N; i++)
        {
            if (!used[i] && board[u][i] != INT_MAX)
            {
                if (dist[u] + board[u][i] < dist[i])
                    dist[i] = dist[u] + board[u][i];
            }
        }
    }
    if (dist[end] == INT_MAX)
        cout << -1 << endl;
    else
        cout << dist[end] << endl;
}

代码中board[i][j]为INT_MAX说明i，j没有连接，我们并非需要遍历所有的顶点，而是遍历所有和S有通路的节点。

邻接表的图

除了用邻接矩阵表示的图可以用dijkstra，邻接表表示的图也可以用dijkstra。

以下是代码：

struct node
{
    int vertex;
    int weight;
    bool operator<(node& a)
    {
        return weight < a.weight;
    }
};
void spaceshipDefence(vector<vector<node>>& adjectTable, int start, int end)
{
    int N = adjectTable.size();
    vector<bool> used(N, false);
    vector<int> dist(N);
    if (start == end)
    {
        cout << 0 << endl;
        continue;
    }
    used[start] = 1;
    for (int i = 0; i < N; i++)
        dist[i] = INT_MAX;
    for (int i = 0; i < adjectTable[start].size(); i++)
    {
        dist[adjectTable[start][i].vertex] = adjectTable[start][i].weight;
    }
    while (true)
    {
        int min_dist = INT_MAX;
        int u = start;
        for (int i = 0; i < N; i++)
        {
            if (!used[i] && dist[i] < min_dist)
            {
                min_dist = dist[i];
                u = i;
            }
        }
        if (u == start)	//没有和S存在通路的未访问顶点了
            break;
        used[u] = true;
        for (int i = 0; i < adjectTable[u].size(); i++)
        {
            if (!used[adjectTable[u][i].vertex])
            {
                if (dist[u] + adjectTable[u][i].weight <
                    dist[adjectTable[u][i].vertex])
                    dist[adjectTable[u][i].vertex] =
                    dist[u] + adjectTable[u][i].weight;
            }
        }
    }
    if (dist[end] == INT_MAX)
        cout << -1 << endl;
    else
        cout << dist[end] << endl;
}

优化

在寻找dist[i]最小的点的时候，我们每次都会遍历所有未访问的顶点，这里是可以进行优化的，我们将未访问的顶点建成一个优先队列就可以每次方便的找到dist[i]最小的值了。

int b;