finding a Critical Path (longest possible path)
Hey people! I'd really appreciate any help you may be able to give me on this problem, I'm not too far off tearing my hair out :)
Basically what i need to do is find the longest possible path through a Graph data structure (edge list implimented), I've looked all over the web for information, and all i could really find out was that the algorithm i need to use is a slightly adapted version of Dijkstra's algorithm.
Thanks in advance for any help i recieve :)
Be more specific.
Do you mean :
- The longest possible path between 2 given nodes when you never visit a node twice?
- The longest possible path between 2 given nodes when you never use an edge twice?
- Given all shortest path between every pair of nodes, what the longest of them?
- Given one node, which of the other node is the farest?
- The longest possible path between in the graph when you never use an edge twice? (Nodes NOT given)
Or something not mentioned?
Sorry, I mean the longest possible path of nodes to visit from a start node to an end node.
In this case the longest path will always be infinite...since you do not have any limiting condition.
Sorry I think I should have explained better, the limiting condition would be an End node, so from some kind of start node, i would need to know the longest path of nodes from the start, through the network of nodes to the end.
this is still infinite , as you can loop between 2 nodes for ever without going to the end point, the contsraint should be something like " dont pass by the same node twice", genetic algorithms and AI may help you. there is a common problem calles "travelling salesman problem" which deals with longest and shortest pathes..
If you have only one cycle in your graph, then the longest path is the one that goes into the cycle and cycles forever (= infinity).
So you need another condition, normally either
- never visit a node twice or
- never use an edge twice
BTW, is your graph weighted? (is the longest path the one with the most nodes in it, or the one with the largest sum of weights?)
he graph is weighted yeah, so the longest path is the one with the highest weightings, it will also have to be acyclic.
You would use Dijkstra's, as you previously mentioned, for this but instead of finding the minimum, you would use the maximum.
Also, it doesn't make sense to use an edge or vertex more than once because, as was previously noted, the length would end up being indefinitely long.
Firstly, it will be best to convert your adjacency list to an adjacency matrix for this implementation.
I have code for the shortest path length, which I have adapted for you for the longest path length. All you would have to do to this code is to make it store the edges in the longest path as well as the length.
Enjoy.
int[][] matrix = // you adjacency matrix
int initialVertex = // the starting vertex.
public int[] getSolution() {
LinkedList used = new LinkedList();
used.add(new Integer(initialVertex));
LinkedList unused = new LinkedList();
for (int i = 0; i < matrix.length; i++) {
if (i != initialVertex)
unused.add(new Integer(i));
}
solution = new int[matrix.length];
for (int i = 0; i < solution.length; i++)
solution[i] = matrix[initialVertex][i];
Integer vertex;
Iterator i;
int value;
while (unused.size() > 0) {
vertex = (Integer)unused.removeFirst();
used.add(vertex);
i = unused.iterator();
while (i.hasNext()) {
value = ((Integer)i.next()).intValue();
solution[value] = (int)Math.max(solution[value],
(solution[vertex.intValue()] +
matrix[vertex.intValue()][value]));
}
}
return solution;
}
Thanks very much mate :) You've saved me an awful lot of grief!
He didn't :(
His algo only works when the vertexes on the longest path are in the same order as they are in the matrix.
If the longest path is (1,3,2,4), it wont be found.
Exaple Distance Matrix:
+ 1 2 3 4
1 0 1 5 10
2 1 0 5 5
3 5 5 0 1
4 10 5 1 0
His algo will give you the response : 10, while the true value is 15.
I'm not shure yet, but I believe this problem is at least in the NP-class, or even truely exponential.
I know that a slighly modified version of the traveling salesman algorithm will solve your problem, but this is in exponential time, therefor I dont know if you really want it.
But if you do, I'll post one.
Otherwise, I'll try to prove that this problem is only solvable in exponential time.
The program i am coding is a project planning system, where the user can create a task to be completed for the project, and the program needs to produce an activity network, similar to a gant chart, where the critical path through the project plan will show as new tasks are added and deleted and dependencies between the tasks are created. I am using the graph data structure because during research into the problem i found out that the structure was very good for creating project planning software.
Anything you can suggest for me to do would be invaluble Phohmeyer.
Thanks again, Minydave - confused coder!
>His algo only works when the vertexes on the longest path are in the same order as they are in the matrix.
And in the case of finding the critical path for a project, this condition can be satisfied, I think. And I doubt that finding the critical path is an NP problem, either. It's much simpler than the general case. Although I could be wrong, that's just my mathematical intuition talking.
Sorry for the late reply.
From your problem describtion, it seams that you have a DAG (a directed acyclic Graph).
The edges are the dependencies and therefor directed.
The graph is also acyclic (It doesn't happen that a task A depends on B and B depends on A).
In this case, you may use dcostakos code, if you garantee that in the unused list, no task is put before one it depends on.
So instead of using a for-loop to put the unused vertexes in the List, use a breath-first parsing (or deep-first, doesn't matter as you will visit every vertex exactly once).
For example :
Set listed = new HashSet; //an Array of booleans would actually be faster.
LinkedList todo = new LinkedList();
todo.add(new Integer(initialVertex);
listed.add(new Integer(initialVertex);
while (l.size() > 0) {
Integer currentVertex = (Integer) l.removeFirst();
Iterator it = getChildrenIterator(currentVertex);
while (it.hasNext()) {
Object chield = it.next();
assert (chield instanceOf Integer);
if (!listed.contains(chield)) {
todo.addLast(chield);
unvisited.addLast(chield);
listed.add(chield);
}
}
}
However, if you do not have a DAG, (if it is not garanteed that there are no cycles in your graph) then the problem becomes NP-complete.
Yeah I will be using a DAG, thanks very much for the help! :)
