rahul_1234's blog

By rahul_1234, history, 6 years ago, In English

You are given a list of edges in a graph and for each pair of vertices that are connected by an edge, there are two edges between them, one curved edge and one straight edge i.e. the tuple (x, y, w1, w2) means that between vertices x and y, there is a straight edge with weight w1 and a curved edge with weight w2. You are given two vertices a and b and you have to go from a to b through a series of edges such that in the entire path you can use at most 1 curved edge.

Your task is to find the shortest path from a to b satisfying the above condition.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Build 2 copies of a directed graph with only straight edges, and add curved edges from vertex a of graph 1 to vertex b of graph 2, now run dijkstra on the new graph.

»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

You didn't indicate if the graph is directed or undirected. Assuming the graph is undirected I have come up with this following solution:

Run dijkstra from node a. Let's call Da[i] be the shortest path to node i from node a using only straight edges.

Again run dijkstra from node b. Let's call Db[i] be the shortest path to node i from node b using only straight edges.

Let ans be our final answer. Initialize ans by Da[b] because this is the answer for using no curved edges.

So ans=Da[b];

Now for using exactly one curved edge we can check for every edge (u,v) by the following way,

ans=min(ans,Da[u]+weight of curved edge (u,v) +Db[v])

ans=min(ans,Da[v]+weight of curved edge (v,u) +Db[u])

Finally ans will be the answer for using at most one curved edge.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    No need to assume it is undirected, The approach works either way.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Found this problem on GFG: Problem Link!

class Solution {
  public:
    int shortestPath(int n, int m, int a, int b, vector<vector<int>> &edges) {
        vector<pair<int, pair<int, int>>> graph[n];
        a -= 1;
        b -= 1;
        for(auto &a : edges){
            a[0] -= 1;
            a[1] -= 1;
            graph[a[0]].push_back({a[1], {a[2], a[3]}});
            graph[a[1]].push_back({a[0], {a[2], a[3]}});
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>,
                            greater<pair<int, int>>> pq;
        int dist[n][2];
        for(int i = 0; i < n; i++)
            dist[i][0] = 1e9, dist[i][1] = 1e9;
        dist[a][0] = 0;
        dist[a][1] = 0;
        pq.push({0, a});
        while( !pq.empty() ){
            auto front = pq.top();
            pq.pop();
            int par = front.second;
            int newDist = front.first;
            for(auto &child : graph[par]){
                int cNode = child.first;
                int curve = child.second.second;
                int st = child.second.first;
                if( dist[cNode][0] > dist[par][1] + curve ){
                    dist[cNode][0] = dist[par][1] + curve;
                    pq.push({dist[cNode][0], cNode});
                }
                if( dist[cNode][0] > dist[par][0] + st ){
                    dist[cNode][0] = dist[par][0] + st;
                    pq.push({dist[cNode][0], cNode});
                }
                if( dist[cNode][1] > dist[par][1] + st ){
                    dist[cNode][1] = dist[par][1] + st;
                    pq.push({dist[cNode][1], cNode});
                }
            }
        }
        int resDist = min(dist[b][0], dist[b][1]);
        if( resDist == 1e9 ) return -1;
        return resDist;
    }
};