Dijkstra's algorithm for the longest path
EDIT 2: It might be too late, but I figured out the problem, it was me. I misunderstood the project, it asked that the largest bandwidth path is not the longest path. which is different, but I didn't know until now. So basically in any bandwidth problem (both the largest and the smallest), the weights do not accumulate, the path value is determined by the smallest weight in the path. Think of it as the path of pipes and the flow of water is determined by the thinnest pipe along the path.
EDIT 1: I fixed the PQ issue but still didn't work.
This is an assignment (I admit), but I could ruin the whole course if I don't submit it. We have to modify Dijkstra's algorithm to compute the longest path SIMPLICITY, not the shortest path. I couldn't find a solution. I searched the internet and found this (it's even the same problem).
But when I run it, it produces wrong values. Is there something I am missing? Why doesn't even he add weight with its predecessor? Why use min?
Information about the graph: 1. We generate the graph at random, so that each node is connected to about 25% of the other nodes. 2. Weights are positive. 3. There are 25 nodes on the graph.
The question says: "The routing algorithm is an algorithm for finding the maximum bandwidth on a graph, based on a modification of Dijkstra's algorithm using the Max-Heap structure." Is there any trick that can help?
public class MaxDijkstra {
Graph graph;
PriorityQueue<Node> queue;
public MaxDijkstra(Graph graph, Node s){
this.graph = graph;
s.addAttribute("ui.class", "start");
queue = new PriorityQueue<>(new Comparator<Node>(){
@Override
public int compare(Node n1, Node n2) {
if(Utils.getNodeBW(n1) == Utils.getNodeBW(n2)){
return 0;
}else if(Utils.getNodeBW(n1) < Utils.getNodeBW(n2)){
return 1;
}else{
return -1;
}
}
});
// init
for(Node n : graph){
Utils.setNodeBW(n, 0);
}
Utils.setNodeBW(s, Float.POSITIVE_INFINITY);
// add to Q
for(Node n : graph){
queue.add(n);
}
while(!queue.isEmpty()){
Node u = queue.remove();
Iterator<Node> iterator = u.getNeighborNodeIterator();
while(iterator.hasNext()){
Node v = iterator.next();
float min = Float.min(Utils.getNodeBW(u), Utils.getEdgeBW(u.getEdgeBetween(v)));
if(min > Utils.getNodeBW(v)){
Utils.setNodeBW(v, min);
Utils.setPreOfNode(v, u);
}
}
// validate PQ
// I know it is not good, just for debuggin now
// I will implemnt my own PQ later
List<Node> list = new ArrayList<>();
while(!queue.isEmpty()){
Node w = queue.remove();
list.add(w);
}
for(Node w : list){
queue.add(w);
}
}
}
public void printInfo(){
for(Node n : graph){
System.out.println("N="+n.getId()+" D="+Utils.getNodeBW(n)+" pre="+ (Utils.getPreOfNode(n) == null ? "NIL" : Utils.getPreOfNode(n).getId()) );
}
}
/**
* Just to colourise the path
* @param target
*/
public void backtrack(Node target){
target.addAttribute("ui.class", "end");
Node currunt = target;
Node pre = Utils.getPreOfNode(currunt);
while(pre != null){
currunt.getEdgeBetween(pre).addAttribute("ui.class", "route");
currunt = pre;
pre = Utils.getPreOfNode(currunt);
}
}
Output example:
Thanks everyone in advance.
source to share
You cannot use Dijkstra's algorithm to find the longest simplest path. This problem is NP-hard. In fact, there is no known polynomial solution there.
If the graph is relatively small, you can use dynamic programming to get a solution O(2^n * poly(n))
, which is possible with n ~ 20-30 (state is the mask of visited vertices and the last vertex. The transition adds one if possible).
If the graph is large, you can use various heuristics and approximations in combination with local optimization techniques to get a good (but not necessarily optimal) solution.
source to share
Try to multiply all weights by -1 so that all weights are negative. Then you can use the Floyd-Warshall algorithm. The Floyd-Warshall algorithm works with negative weights in a graph that has no cycle. So, use Floyd-Warshall to find the smallest path that, when multiplied by -1, will be your maximum path in the original graph.
source to share
You cannot modify items already in the priority queue. Usually for Dijkstra you need a function decrease key
, but one of the library doesn't support that, so you can just re-insert nodes multiple times in pq with different BW values. Something like this (treat it as pseudocode :))
PriorityQueue<pair<Node, int>> queue;
public MaxDijkstra(Graph graph, Node s){
queue = new PriorityQueue<>(new Comparator<pair<Node, int>>(){
@Override
public int compare(pair<Node, int> n1, pair<Node, int> n2) {
return n1.second > n2.second;
}
});
// init
for(Node n : graph){
Utils.setNodeBW(n, 0);
}
Utils.setNodeBW(s, Integer.MAX_VALUE);
// add to Q
for(Node n : graph){
queue.add({n, n.getNodeBW()});
}
while(!queue.isEmpty()){
pair<Node, int> u = queue.remove();
if (u.second < u.first.getNodeBW()) continue; //important - skip if you already saw better value
Iterator<Node> iterator = u.getNeighborNodeIterator();
while(iterator.hasNext()){
Node v = iterator.next();
int min = Integer.min(Utils.getNodeBW(u), Utils.getEdgeBW(u.getEdgeBetween(v)));
if(min > Utils.getNodeBW(v)){
Utils.setNodeBW(v, min);
queue.insert({v, min});
}
}
}
}
}
source to share