## Introduction

A common prerequisite before any graph problem is the knowledge of graphs and related terminologies such as recursion, stacks, queues, trees, and the 2 standard algorithms __DFS Algorithm__, BFS, and topological sorting. Without knowing these basic algorithms and data structures, jumping on to the shortest path problems in graphs is not recommended.

Nevertheless, we’ll try to cover each point in-depth that is required to find the **shortest path in a directed acyclic graph**.

What do we mean by the Shortest Path in a directed acyclic graph?

Well, it’s a trivial question, but still, for the sake of clarity, we’ll define that let

**G = (V, E)** be a directed graph with **E** edges and **V **vertices.

Let **T** be the shortest path between any 2 vertices in the graph such that there is no other path in the graph between any 2 vertices whose sum of edge weights is less than **T’**s sum of edge weights.

**NOTE**: shortest path between 2 vertices is defined only when the vertices are in the same graph, i.e., the graph should not be disconnected.

Let’s look at an example first.

**Given a weighted DAG G**,

Input: Starting Node Src = 1

Output: List of shortest distances denoting the shortest path from ‘Src’ to all other nodes in the DAG.

For the above DAG, we will return {INF, 0, 2, 6, 5, 3}

So the problem is to find the shortest path from a given source to All other nodes in the weighted DAG.

## Approach

What is the first approach that comes to our mind? Don’t think about any optimizations for now. The first solution that will strike anybody’s mind is from the given ‘src’ node to find the shortest path to each node one by one. For all paths from source to a particular destination node, we will choose the shortest path.

Let’s walk through this solution in the above example.

So the given Source node is 1. Say T_{src - dest}^{i} → denotes the ith path from the ‘src’ node to a particular destination node.

For dest = 0,

There is no path, so the shortest path has weight INF.

For dest = 1,

There is no external path, but the distance from ‘src’ - ‘src’ is trivial, i.e., = 0.

For dest = 2,

T_{1 - 2}^{1} = 1 -> 2, it’s the only path from ‘src’ node to dest node, hence shortest path has weight = 2.

For dest = 3,

T_{1 - 3}^{1} = 1 -> 3, it has distance = 6

T_{1 - 3}^{2} = 1 -> 2 -> 3, it has distance = 9

So the shortest distance of the 2 paths is 6.

For dest = 4,

T_{1 - 4}^{1} = 1 -> 3 -> 4, it has distance = 5

T_{1 - 4}^{2} = 1 -> 2 -> 3 -> 4, it has distance = 8

T_{1 - 4}^{3} = 1 -> 2 -> 4, it has distance = 6

So the shortest distance of the 3 paths is 5.

For dest = 5,

T_{1 - 5}^{1} = 1 -> 2->5, it has distance = 4

T_{1 - 5}^{2} = 1 -> 3 -> 4 -> 5, it has distance = 3

T_{1 - 5}^{3} = 1 -> 2 -> 3 -> 4 -> 5, it has distance = 6

T_{1 - 5}^{4} = 1 -> 2 -> 4 -> 5, it has distance = 4

So the shortest distance of the 4 paths is 3.

So we will compute the distances from the given ‘src’ node to all other nodes in a similar manner as we walked through the example.

Hence now we can formulate our approach for the brute-force approach:

- For a particular node, compute distances of all possible paths from the given ‘src’ node.
- From the calculated distances, find the minimum of them.
- Repeat the same process for all the other nodes in the DAG

### PseudoCode

# Assume that the function computeAllDistances(Src, Dest) returns all possible path distances from Src to Dest.

**Algorithm**

```
___________________________________________________________________
procedure ShortestPathInDAG(Graph G, Src):
___________________________________________________________________
1. Shortest_path_distances ← empty list # final list that will be returned
2. for each vertex v in G.V do
3. List_of_all_possible_path_dists ← computeAllDistances(G, Src, v)
4. If List_of_all_possible_path_dists is not empty do
5. Shortest_path_distances[v] ← min(List_of_all_possible_path_dists)
6. end if
7. else
8. Shortest_path_distances[v] ← INF
9. end else if
10. return Shortest_path_distances
11. end procedure
___________________________________________________________________
```

The above approach is undoubtedly not efficient, as you can see the repetitive computations being made for calculating distances for each node. Let’s look at some efficient algorithms which can solve the same problem efficiently.