# Shortest path using less than or equal to m edges in a directed, weighted graph with negative cycles

I’m solving a problem:

Given a directed, weighted graph $$G$$ that has $$V$$ vertices and $$E$$ edges and a positive integer $$m$$, describe an algorithm that finds the length of the shortest path using less than or equal to $$m$$ edges. Note that the graph may contain negative cycles.

First, I tried Bellman-Ford algorithm, but I cannot deal with negative cycles. Next, I tried one using recursive DFS, but it takes too much time! I think dynamic programming may solve this problem, but I don’t know how to start with DP. Is there any fancy way to solve this problem in short time?