Exact Algorithm for edge labeling problem in DAG
havent heard of this problem exactly in literature [maybe someone else has] however as a "nearby problem" it seems to me the minimum spanning tree would have useful properties to solve your problem. for example maybe generating two minimum spanning trees starting from the source vertex &amp; the sync vertex, and propagating them outward until they touch, etc. might solve the problem or give a close answer. before anyone dings me on this here plz understand I am extending the idea of the MST somewhat to be generated starting from a given vertex [normally it starts from shortest edge in the entire graph]. if it doesnt work Id be curious for the reason.