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的算法。可能有一种更有效的方法可以一次性完成，但这会让您入门。