dijkstra can be applied for longest pathif there is no cycle..
now assuming that it is directed acyclic graph(DAG)
if u multiply all weights by -1...means all weights are negative..then apply
dijkstra for shortest path and u will get your answer
--
You received this message because you ar
If you negate the values, then it will loop on forever in a cycle, as adding
more negative values *seems* to give shorter path.
2010/1/15 chitta koushik
> How abt negating values and using same single source shortest path algo ?
>
> 2010/1/15 saltycookie
>
>> longest path is NP-hard
>>
>> 2010/
longest path can be solved in acyclic directed graphs.
so check your case if it is not that.
2010/1/15 Vivek S
> @chitta koushik
> No, That might lead to negative edge cycles!
>
> 2010/1/15 chitta koushik
>
>> How abt negating values and using same single source shortest path algo ?
>>
>> 2010/
@chitta koushik
No, That might lead to negative edge cycles!
2010/1/15 chitta koushik
> How abt negating values and using same single source shortest path algo ?
>
> 2010/1/15 saltycookie
>
>> longest path is NP-hard
>>
>> 2010/1/11 Johan
>>
>>> Ok, so I know that Dijkstra can be used to solve
How abt negating values and using same single source shortest path algo ?
2010/1/15 saltycookie
> longest path is NP-hard
>
> 2010/1/11 Johan
>
>> Ok, so I know that Dijkstra can be used to solve the single-source
>> shortest path problem quite efficiently. I however need to find the
>> single
No. The normal Dijkstra's cannot be modified to work for longest path, as
you can see the optimal subproblem problem is not satisfied. While the
Dijkstra's shortest path can be computed in polynomial time, the longest
path cannot be ( NP complete ). I'm sure there are lot of resources on net.
May b
longest path is NP-hard
2010/1/11 Johan
> Ok, so I know that Dijkstra can be used to solve the single-source
> shortest path problem quite efficiently. I however need to find the
> single source longest path through a graph. Can Dijkstra be used for
> this if I transform the edge lengths so that
Ok, so I know that Dijkstra can be used to solve the single-source
shortest path problem quite efficiently. I however need to find the
single source longest path through a graph. Can Dijkstra be used for
this if I transform the edge lengths so that the longest edge is now
the shortest etc etc. Does
