**Problem Statement: **

You are given a network of `n`

nodes, labeled from `1`

to `n`

. You are also given `times`

, a list of travel times as directed edges `times[i] = (u`

, where _{i}, v_{i}, w_{i})`u`

is the source node, _{i}`v`

is the target node, and _{i}`w`

is the time it takes for a signal to travel from source to target._{i}

We will send a signal from a given node `k`

. Return *the minimum time it takes for all the*

`n`

*nodes to receive the signal*. If it is impossible for all the

`n`

nodes to receive the signal, return `-1`

.

**ELI5**

Just find the shortest path between the given node n to all the other nodes. When i am writing this post, i have no idea about djisktra, i am going to read about djikstra, develop my own intuition then apply on this problem

**Trying to solve..**

First i would like to create a graph data structure from the given input, so i just created a dict where each key is a node and values will be the nodes which are connected to the node in k.

Now we have a dictionary which kind of feels like a linked list, i.e we just have a node which is connected to other nodes.

**How our result look like ? **

we just need to return a list of times, so we will initialize that

why float("inf") ? there is a edge case where reaching all nodes might not be possible, this times will be used to store numbers, initializing it to infinity seems logical because times is in range of 1 to 6000 in this case, this infinity can represent node is not reachable instead of using None, in that case i would need to perform a type check every time when i need to access the value.

**Base Case**

I am sending the signal from node k, so the time taken to reach the node k from k would always obviously be 0, lets code that up

k-1, because arrays start from 0

**Brute Force: **

Before starting to perform any sort of iterations, i want to** **keep a list of vertices i visit, because i dont want to end up in a cycle** **where the code would run forever, what i meant is take this example graph

If we start from A and compute min distance between A and B, then we go to B and find C and from C we will find A again. How do you prevent this from happening? The obvious way to do this is by remembering which nodes you visited.

Thats ok we can keep a list, but we would need O(n) time to query that list. Ok scratch that, we can use a set, it just takes O(1) lookup time.

Alright, all set to start and fail with our brute force solution.

Steps:

1. We will start with node k, explore the neighbours of k

2. Then we will collect all of them in to a list

3. Then we start exploring elements in list and then add back the newly found nodes in the queue.

4. If the node is already in visited then we dont need to visit it again.

This now does the basic breadth first search on the graph. This doesnt calculate the time it took for the signal to travel, lets include that logic in the code

time took to reach child node = time took to travel from parent to child node + existing time which will use to reach its children

we are updating this since the signal is transmitted from node k. When we are updating time we also need to check if that could be the minimum time to reach the node, lets do that with few lines of code

alright, i guess we completed the code, lets run it

after submission i got error on this test case

i am quite surprised, i was under the impression that i covered all the edge cases, ok lets visualize

I left this edge unexplored, because according to my logic visited nodes should not be visited again, but i am not sure how would i be able to prevent the cycle if i cant keep track of visited nodes.. i could formulate some thing like this, if i reach the initial node again, then its a cycle since i started from k

That doesnt get me far, this is too big to visualize but i am sure i got hit by this edge case

Any nodes which are not the start pointed at each other, ok its very clear that i need to maintain a visited set, we are back to square one.

What i want to do is to find the minimum edge, may be i can explore this edge if its less than previous distance ?

Lets go back to this failing test case

here i didnt explore edge with weight 2 since i had visited 3 via edge with weight 4. i think i can change this condition

to

if you hate this nested array comparison syntax you are not alone, i hate it too.

Usually in production code i would probably make this in to a helper method which will be more readable. But in terms of psuedo code this exactly what i am writing

```

if node is not visited or time took to visit the node is greater than our current path

```

We explore the same node again if that condition matches, lets submit

Boom, it worked :-)

This completes our brute force solution, lets analyze why this very inefficient before moving to djisktra

In the green i marked the distance of nodes when starting from A. The distances are marked before discovering our edge B - C which has distance of 2.Once its discovered now every edge leaving C must be recomputed. The reason is we discovered a shortest path to C. Before discovering that edge the shortest path to D would be 10, after discovering the edge it will just be 4

The brute force solution is inefficient because once we discover a shortest path to a node, then we have to recompute all the edges leaving that node. This is exactly what we will try to optimize.

When i thought about this, i was wondering why we need to visit all the paths from node C if the shortest path to C is discovered, we could simply skip it. But then i realized the distance from A is computed by adding these edge lengths on level by level.

So when you discover a shortest path to a node, then all of its children needs to be revisited.

**How to do that ?**

Lets say there are three edges leaving A to C, each has distinct weight 1,2,3

Which edge you would choose so that you dont have recalculate the nodes starting from C? Thats easy we can go with edge 1, because other edges are greater than this edge. So we would never have to recompute the nodes connected from C. Well thats about it, we just discovered djisktra algorithm. We just need to apply this optimization over our bruteforce solution.

The solution stays same, instead of a simple list we are going to use min_heap to store nodes. This will not explore nodes level by level, we are going to put the nodes we discover in to our min heap, we will pick the one which has the minimum value.

thats about it, we implemented djisktra optimization over our bruteforce solution. The major thing we prevented is number of times the distance is recomputed once a minium length to node is discovered.

## 0 comments:

## Post a Comment