Hi, Aziz.

I am supposing that with "evaluate the complexity" you mean a worst case analysis (big O). Thus, to consider a worst case time complexity analysis, the graph instance would not have any weighted edge exceeding the given limit. So, the algorithm would behave just like the non-constrained one. In this case, the time complexity will depend on which algorithm you are implementing (Dijkstra, Floyd-Warshall, Bellman-Ford, ...).

I hope this helps you!

Jody

Hi, 

If you are applying the evolutionary algorithm, the big(O) may not be suitable though. You are searching for a solution, an estimation. 

Nonetheless, this problem definition reminds me of neural networks. It is perhaps one way forward.

Patricia

Hi Jody,

Yes I am evaluating the "big O" and using Dijkstra algorithms. However, we add the weight of each added link to the path until it reach some limit, if the destination is reached we return the shortest path, if not, we return null.

If the graph is large in size, we do not need to search the whole graph like unconstrained algorithms. This make the "big O"  of our algo. different.

Thnaks 

Hi, Aziz.

You have just explained in details exactly what I understood in your first message. Thus, let me try to make myself clear. 

Once a "big O" analysis shall consider the worst case time complexity when running the analysed algorithm, I understood that the worst case of your algorithm would be the case in which the weight limit is not reached and the algorithm would stay running for the whole graph. In this case, the "big O" analysis gives you the same complexity of the standard algorithm (Disjkstra, as you said). I mean, your algorithm may be different for number of cases, but not necessarily different to the worst case.

Another option you have is to analyse the average-case complexity. In this analysis, you may also consider specific characteristics that the type of graph you are working may have. It can simplify the average-case analysis and provide you a more realistic analysis.

Jody

Thank you very much Jody,

• Anyone has another idea is welcome . . .

Hi, This may help you.

http://www.geeksforgeeks.org/shortest-path-exactly-k-edges-directed-weighted-graph/

Good luck

http://www.geeksforgeeks.org/shortest-path-exactly-k-edges-directed-weighted-graph/

Thanks Waqas