Created
August 15, 2019 17:03
-
-
Save RitamChakraborty/b9cf2940dbf364701ef96036acc3cd79 to your computer and use it in GitHub Desktop.
Multistage Graph problem using java. Get the minimum cost for going from one vertex to another.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.*; | |
import java.util.stream.*; | |
class Neighbour { | |
public Node node; | |
public int weight; | |
Neighbour(Node node, int weight) { | |
this.node = node; | |
this.weight = weight; | |
} | |
@Override | |
public String toString() { | |
return node.toString(); | |
} | |
} | |
class Node { | |
public int index; | |
public List<Neighbour> neighbours; | |
Node(int index) { | |
this.index = index; | |
} | |
public void setNeighbours(Neighbour... neighbours) { | |
this.neighbours = Arrays.stream(neighbours).collect(Collectors.toList()); | |
} | |
@Override | |
public String toString() { | |
return Integer.toString(index); | |
} | |
} | |
class MultistageGraph { | |
public static int cost(Node v) { | |
if (v.index == 8) { | |
return 0; | |
} else { | |
return Collections.min(v.neighbours.stream().map(i -> cost(i.node) + i.weight).collect(Collectors.toList())); | |
} | |
} | |
public static int cost(Node startingNode, Node destinationNode) { | |
return cost(startingNode); | |
} | |
public static void main(String[] args) { | |
Node v1 = new Node(1); | |
Node v2 = new Node(2); | |
Node v3 = new Node(3); | |
Node v4 = new Node(4); | |
Node v5 = new Node(5); | |
Node v6 = new Node(6); | |
Node v7 = new Node(7); | |
Node v8 = new Node(8); | |
v1.setNeighbours( | |
new Neighbour(v2, 2), | |
new Neighbour(v3, 1), | |
new Neighbour(v4, 3) | |
); | |
v2.setNeighbours( | |
new Neighbour(v5, 2), | |
new Neighbour(v6, 3) | |
); | |
v3.setNeighbours( | |
new Neighbour(v5, 6), | |
new Neighbour(v6, 7) | |
); | |
v4.setNeighbours( | |
new Neighbour(v5, 6), | |
new Neighbour(v6, 8), | |
new Neighbour(v7, 9) | |
); | |
v5.setNeighbours( | |
new Neighbour(v8, 6) | |
); | |
v6.setNeighbours( | |
new Neighbour(v8, 4) | |
); | |
v7.setNeighbours( | |
new Neighbour(v8, 5) | |
); | |
System.out.println(cost(v1, v8)); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment