路径受阻的 Dijkstra SSSP

Question

我正在研究这个问题，我决定使用 Dijkstra 算法来解决它。但是，我不确定如何解释从 a 到 b 的阻塞路径以及路径阻塞时如何解释 60 分钟的等待时间。我需要多个 SSSP 来解决这个问题吗？我该如何解决这个问题？

图片来源：新加坡国立大学

我的代码如下：

struct road_tuples{
    int u;
    int v;
    int w;
};

int minDistance(int dist[], bool sptSet[], int V){
    int min = INT_MAX;
    int min_index;
    for(int v = 0; v<V;v++){
        if(sptSet[v]==false && dist[v]<=min){
            min = dist[v];
            min_index  = v;
        }
    }
    return min_index;
}
//dijkstra using adj matrix
int minMinutes(int V, int a, int b, int c, int d, int E, road_tuples list){
    //create adjacency matrix
    int graph[V][V];
    //fill in adjacency matrix
    for(int i=0;i<E;i++)
        graph[list.u][list.v] = list.w;
        graph[list.v][list.u] = list.w;
    //no path from a to b
    graph[a][b] = 0;
    graph[b][a] = 0;
    //assign source
    int src = c;
    //will hold shortest distance from src to i
    int dist[V];
    //sptSet[i] will be true if i included in SSSP
    bool sptSet[V];
    //init all distances to infinite, set sptSet[i] as false
    for(int i =0; i < V; i++){
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }
    //set dist from source to itself as 0
    dist[src] = 0;
    //find shortest path for all vertices
    for(int count =0; count< V-1; count++){
        int u  = minDistance(dist, sptSet, V);
        sptSet[u] = true;
        for(int v=0; v<V; v++){
            if(!sptSet[v] && graph[u][v] && dist[u]!= INT_MAX
               && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
        }
    }

    return dist[d];
}

Answer 1

好的，所以你需要做的是找到从机场到目的地的最短路径，然后将路径中的所有边都加上 60，然后从你家开始再次执行迪杰斯特拉算法，然后去办公室。可能有一种更有效的方法可以一次完成，但这会让你开始。

路径受阻的 Dijkstra SSSP

Dijkstra SSSP with blocked path

c++

algorithm

dijkstra

shortest-path

data-structures