15-1 Longest simple path in a directed acyclic graph

Suppose that we are given a directed acyclic graph \(G = (V, E)\) with real-valued edge weights and two distinguished vertices \(s\) and \(t\) . Describe a dynamic-programming approach for finding a longest weighted simple path from \(s\) to \(t\). What does the subproblem graph look like? What is the efficiency of your algorithm?

Since any longest simple path must start by going through some edge out of \(s\), and thereafter cannot pass through \(s\) because it must be simple, that is,

with the base case that if \(s = t\) then we have a length of \(0\).

A naive bound would be to say that since the graph we are considering is a subset of the vertices, and the other two arguments to the substructure are distinguished vertices, then, the runtime will be \(O(|V|^2 2^{|V|})\). We can see that we will actually have to consider this many possible subproblems by taking \(|G|\) to be the complete graph on \(|V|\) vertices.

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用