CODEWITHSUNDEEP
c++data-structuresbreadth-first-search
Chaitanya Gujarathi
Chaitanya Gujarathi

Reputation: 157

BFS solution giving wrong answer to network time problem

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

here is my code.. however it is giving wrong answer

class Solution {
public:
    int networkDelayTime(vector <vector<int>> &times, int N, int K) {

        vector<int> time(N + 1);
        vector<int> visited(N + 1, 0);
        vector < vector < pair < int, int >> > graph(N + 1);
        for (int i = 0; i < times.size(); i++) {
            graph[times[i][0]].push_back(make_pair(times[i][1], times[i][2]));
        }

        queue <pair<int, int>> q;
        q.push(make_pair(K, 0));
        visited[K] = 1;
        time[K] = 0;
        while (!q.empty()) {
            int end = q.front().first;
            int duration = q.front().second;
            q.pop();
            for (auto k:graph[end]) {
                int first = k.first;
                int second = k.second;
                if (!visited[first]) {
                    q.push(make_pair(first, second));
                    time[first] = duration + second;
                    visited[first] = 1;
                } else {
                    time[first] = min(time[first], (duration + second));
                }
            }
        }
        for (int i = 1; i <= N; i++) {
            if (visited[i] == 0) {
                return -1;
            }
        }
        sort(time.begin(), time.end());
        return time[N];
    }
};

I am not able to figure out where I am wrong. Thanks

Upvotes: 0

Views: 106

Answers (1)

Daniel
Daniel

Reputation: 7724

This is a text-book application of Dijkstra's algorithm.

Given a node K, this algorithm will fill an array with the minimum distance from K to every other node, so the biggest value in this array will be the total time it takes for the signal to reach every other node.

You can't just use a BFS because it won't necessarily consider a shorter path to a node once it has already found any other path to that node. Dijkstra's algorithm is a modification of the BFS that deals with that. See this example, supposing the initial node is 1, the distances to the other nodes given by BFS and Dijkstra are different:

enter image description here

Upvotes: 2

Related Questions