Dijkstra

Dijkstra算法是一种用于计算单源最短路径的经典算法。以下是该算法的C++实现：

void Dijkstra(vector<vector<int>>& A, int v, int n) {
    vector<int> dist(n);
    vector<bool> S(n);
    //初始化
    for (int i = 0; i < n; i++) {
        dist[i] = A[v][i];
        S[i] = false;
    }
    S[v] = true;
    // 对剩下的n-1个顶点进行处理
    for (int i = 0; i < n-1; i++) {
        int mindis = INT_MAX;
        int u = -1;

        for (int j = 0; j < n; j++) {
            if (!S[j] && dist[j] < mindis) {
                mindis = dist[j];
                u = j;
            }
        }
        if (u == -1) break;  // 找不到就退出
        S[u] = true;  // 否则就标记为true
        // 更新其他顶点的到源点的距离
        for (int j = 0; j < n; j++) {
            if (!S[j] && A[u][j] != INT_MAX && 
                dist[u] != INT_MAX && 
                dist[u] + A[u][j] < dist[j]) {
                dist[j] = dist[u] + A[u][j];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << dist[i] << " ";
    }
}

最近刚学，简单记录一下。