Re: Longest path

For the first problem, it is equivilent to finding shortest path for a
similar graph with all edges values negated. Problem is, you can't use
dijkstra, because there might be negative-sum circules, which is a
problem, since the shortest path will go through this circle inifinte
number of times. You can use Bellman-Ford though, which works a little
slower (O(VE)), but finds out if there are negative-sum circles.
Im not sure, but you asked for an algorithm to find the longest SIMPLE
path, so you might wanna find one even though there is a negative-sum
circle, so that's gonna be a problem.

For the second problem, If I understand you correctly, you want to
find whether a graph has two parts which are not connected by any
edge. You can just do a DFS starting from an arbitrary vertex, and if
you still have uncolored vertices, then this graph can be divided into
two (or more) parts.

.

Relevant Pages

  • Re: Shortish paths
    ... original graph. ... The functionality of Dijkstra's original algorithm can be extended ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)
  • Re: Shortish paths
    ... For how many nodes and how many edges will the actual algorithm run ... original graph. ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)
  • Finding shortest path into unweighted undirected graph
    ... that way we can say the graph is unweighted and undirected, ... Almost every algorithm I've found on the net is for directed, ... to node A. We say node A is the center of that circle. ... Lets build trees from nodes - each ...
    (comp.games.development.programming.algorithms)
  • Finding shortest path into unweighted undirected graph
    ... that way we can say the graph is unweighted and undirected, ... Almost every algorithm I've found on the net is for directed, ... to node A. We say node A is the center of that circle. ... Lets build trees from nodes - each ...
    (sci.math)
  • Re: a circumference is a function?
    ... no; it is a circle. ... "graph" of a function. ... The key word here is "valid". ... A real function of real variable is one in which every valid input is ...
    (sci.math)