Dijkstra

Dijkstra

Dijkstra算法是一种用于计算单源最短路径的算法，适用于加权图（无负权边）。

Dijkstra的主要目标是找到从源节点到所有其他节点的最短路径，也就是找到以该点为起点，其他节点为终点的最短长度。

Dijkstra原理

Dijkstra算法的核心思想是通过逐步扩展已知的最短路径来找到从源节点到所有其他节点的最短路径。Dijkstra算法维护一个已经确定的最短路径的顶点的集合和一个未确定最短路径的顶点的集合。Dijkstra通过不断选择未确定集合中距离源节点最近的节点来更新其临接节点的距离

Dijkstra步骤

1. 初始化

   创建一个距离数组dist数组，用于存储各个节点到源节点的最短距离。初始化为源节点到源节点的距离为0，其他节点到源节点的距离为无穷大

   创建一个优先队列（通常使用最小堆）来存储未确定的节点，初始时将源节点加入队列

2. 选择节点

   从优先队列中提取距离最小的节点（称为当前节点），并将其标记为已确定

3. 更新距离

   对于当前节点的每一个邻接节点，如果通过当前节点到达该邻接节点的距离小于已知的距离，则更新该邻接节点的距离，并将其加入优先队列

4. 重复

   重复步骤 2 和 3，直到优先队列为空，表示所有节点的最短路径都已确定。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
const int N = 1010;
vector<pair<int,int>> graph[N];
int dijikstra(int n)
{
    vector<int> dist(n+1,INT_MAX);
    dist[1] = 0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    pq.push({0,1});//表示第一个节点，权重为0
    while(!pq.empty())
    {
        int current_distance = pq.top().first; // 当前最小距离
        int current_node = pq.top().second; // 当前节点
        pq.pop();
        // 如果当前距离大于已知距离，跳过
        if (current_distance > dist[current_node]) {
            continue;
        }

        for(const auto &edge : graph[current_node])
        {
            int neighbor = edge.first; // 邻接节点
            int weight = edge.second; // 边的权重
            int new_distance = current_distance + weight;
            // 如果找到更短的路径，更新距离并加入优先队列
            if (new_distance < dist[neighbor]) {
                dist[neighbor] = new_distance;
                pq.push({new_distance, neighbor});
            }
        }
    }
    return dist[n];
}

int main()
{
    int V,E;
    cin >> V >> E;
    for(int i = 0 ; i < E ; i ++)
    {
        int v1,v2,weight;
        cin >> v1 >> v2 >> weight;
        graph[v1].emplace_back(v2,weight);
    }
    int res = dijikstra(V);
    if(res == INT_MAX) cout << "-1";
    else cout << res << endl;
    return 0;
}