Skip to content

Instantly share code, notes, and snippets.

@RitamChakraborty
Created August 15, 2019 17:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save RitamChakraborty/b9cf2940dbf364701ef96036acc3cd79 to your computer and use it in GitHub Desktop.
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.
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