Dijkstra（迪杰斯特拉算法）

xiufanivan · 2023-03-29 19:53:19 · 个人记录

视频讲解： dijstra算法 - bilibili

路径图：

graph TD
    0((0)) --10--> 2((2)) --5--> 1((1))
    0((0)) --30--> 4((4)) --20--> 3((3)) --10--> 5((5))
    2((2)) --50--> 3((3))
    0((0)) --100--> 5((5))
    4((4)) --60--> 5((5))

代码：（邻接矩阵）

#include <iostream>
using namespace std;

// 邻接矩阵 
int mp[6][6] = {{1000000, 1000000, 10,      100000,  30,      100},
                {1000000, 1000000, 1000000, 1000000, 1000000, 1000000},
                {1000000, 5,       1000000, 50,      1000000, 1000000},
                {1000000, 1000000, 1000000, 1000000, 1000000, 10},
                {1000000, 1000000, 1000000, 20,      1000000, 60},
                {1000000, 1000000, 1000000, 1000000, 1000000, 1000000}
                };
bool vis[10] = {false};  // 是否已确定最短路径，
int dis[10];  // 最短路径长度 

void shortestPath(int s) {  // 起点s到其他点的最短路径 
    dis[s] = 0;  // 起点设置为0
    vis[s] = true;
    // 用起点指向的结点，更新dis
    for (int i = 0; i <= 5; i++) {
        if (mp[s][i] < dis[i]) {
            dis[i] = mp[s][i];
        }
    }

    while (true) {
        // dis中找出未确定最短路径的最小的点
        int min_i = 0, min_v = 1000000;
        for (int i = 0; i <= 5; i++) {
            if (!vis[i] && min_v > dis[i]) {
                min_i = i;
                min_v = dis[i];
            }
        }
        // vis全为true，最短路径全部找出 
        if (min_i == 0) {
            break;
        }
        vis[min_i] = true;
        // 更新min_i结点所指向的结点的最短路径数组，即dis
        for (int i = 0; i <= 5; i++) {
            if (!vis[i] && dis[i] > dis[min_i] + mp[min_i][i]) {
                dis[i] = dis[min_i] + mp[min_i][i];
            }
        }
    } 
} 

int main() {
    // 初始化为无穷大 
    for (int i = 0; i <= 5; i++) {
        dis[i] = 1000000; 
    }
    shortestPath(0);

    for (int i = 0; i <= 5; i++) {
        cout << dis[i] << " ";
    }
    cout << endl;

    return 0;
}

代码：（邻接表）

#include <iostream>
#include <vector>
using namespace std;

struct Node {
    int v, len;
    Node(int v, int len) {
        this->v = v;
        this->len = len;
    }
};

// 邻接表 
vector<vector<Node> > mp(6, vector<Node>());

bool vis[10] = {false};  // 是否已确定最短路径，
int dis[10];  // 最短路径长度 

// 邻接表初始化 
void init_v() {
    mp[0].push_back(Node(2, 10));
    mp[0].push_back(Node(4, 30));
    mp[0].push_back(Node(5, 100));
    mp[2].push_back(Node(1, 5));
    mp[2].push_back(Node(3, 50));
    mp[3].push_back(Node(5, 10));
    mp[4].push_back(Node(3, 20));
    mp[4].push_back(Node(5, 60));
}

void shortestPath(int s) {  // 起点s到其他点的最短路径 
    dis[s] = 0;  // 起点设置为0
    vis[s] = true;

    for (int i = 0; i < mp[s].size(); i++) {
        if (mp[s][i].len < dis[mp[s][i].v]) {
            dis[mp[s][i].v] = mp[s][i].len;
        }
    }

    while (true) {
        // dis中找出未确定最短路径的最小的点
        int min_i = 0, min_v = 1000000;
        for (int i = 0; i <= 5; i++) {
            if (!vis[i] && min_v > dis[i]) {
                min_i = i;
                min_v = dis[i];
            }
        }
        // vis全为true，最短路径全部找出 
        if (min_i == 0) {
            break;
        }
        vis[min_i] = true;
        // 更新min_i结点所指向的结点的最短路径数组，即dis
        for (int i = 0; i < mp[min_i].size(); i++) {
            if (!vis[mp[min_i][i].v] && dis[mp[min_i][i].v] > dis[min_i] + mp[min_i][i].len) {
                dis[mp[min_i][i].v] = dis[min_i] + mp[min_i][i].len;
            }
        }
    } 
} 

int main() {
    // 初始化为无穷大 
    for (int i = 0; i <= 5; i++) {
        dis[i] = 1000000; 
    }
    // 邻接表初始化 
    init_v();

    shortestPath(0);

    for (int i = 0; i <= 5; i++) {
        cout << dis[i] << " ";
    }
    cout << endl;
    for (int i = 0; i <= 5; i++) {
        cout << vis[i] << " ";
    }
    cout << endl;

    return 0;
}