## How do you find the longest path in an unweighted DAG?

The recursive formula will be: dp[node] = max(dp[node], 1 + max(dp[child1], dp[child2], dp[child3]..)) At the end check for the maximum value in dp[] array, which will be the longest path in the DAG.

**Does DFS Give longest path?**

There is this standard algorithm for finding longest path in undirected trees using two depth-first searches: Start DFS from a random vertex v and find the farthest vertex from it; say it is v′. Now start a DFS from v′ to find the vertex farthest from it. This path is the longest path in the graph.

**How do you use Dijkstra’s algorithm to find the longest path?**

You need to find a value at least equal to the maximum weight, and then for each weight: weight = max_weight – weight. Then a normal Dijkstra will return you the longest path. Just do path_length*max_weight – dist to get that distance.

### How do you find the longest path in a tree?

- Run DFS from any node to find the farthest leaf node. Label that node T.
- Run another DFS to find the farthest node from T.
- The path you found in step 2 is the longest path in the tree.

**How do you find the longest path on a cyclic graph?**

To find the longest path in a directed, cyclic graph, G = ( V , E ) G = (V, E) G=(V,E) (as asked in Coding Assignment 4 part e), I implemented an algorithm which generates a number of permutations of DAG reductions, G π G_{\pi} Gπ, of the graph G, and finds the longest path in each of these DAGs.

**What is Kahn’s algorithm?**

Essentially, Kahn’s algorithm works by keeping track of the number of incoming edges into each node (indegree). It repeatedly: Finds nodes with no incoming edge, that is, nodes with zero indegree (no dependency). Stores the nodes with zero indegree in a stack/queue and deletes them from the original graph.

#### Why is longest path hard?

If there is a negative cycle in -G , a longest path does not exist at all in G , because you can just continue walking around the cycle forever. A longest simple path might still exist, but with or without negative cycle, the problem can be reduced to Hamiltonian Path and is therefore still NP-hard.

**Can BFS find longest path?**

We don’t. BFS essentially finds the shortest path between a vertex and all other vertices in a graph and therefore doesn’t work for the longest path problem.

**How do you find the longest path in a DAG?**

For a DAG, the longest path from a source vertex to all other vertices can be obtained by running the shortest-path algorithm on −G. Similarly, for each vertex v in a given DAG, the length of the longest path ending at v may be obtained by the following steps: Find a topological ordering of the given DAG.

## Can Dijkstra be used to find longest path in a graph Mcq?

Yes, with a slight modification to the algorithm.

**How do you find the longest path between two nodes in a tree?**

A correct algorithm is:

- Run DFS from any node to find the farthest leaf node. Label that node T.
- Run another DFS to find the farthest node from T.
- The path you found in step 2 is the longest path in the tree.