Intro
A probabilistic graph \$G = (V, E)\$ is an undirected graph with weight function \$w \colon E \rightarrow [0, 1]\$. In the most reliable path problem we -- given two terminal nodes \$s \in V\$ and \$t \in V, t \neq s\$ -- we wish to find the most reliable/probable path connecting \$s\$ and \$t\$. Basically, we solve it via Dijkstra's algorithm with a minor but an important tweak: when we consider a weight \$p = w(u, v)\$ of an undirected edge \$(u, v)\$ we reset it to \$-\log(p)\$. Note that:
- $$\lim_{p \rightarrow 0+} (-\log(p)) = \infty,$$
- $$\lim_{p \rightarrow 1-} (-\log(p)) = 0,$$
- $$\{-\log(p) \; \colon \; p \in [0, 1]\} = [0, \infty].$$
Code
io.github.coderodde.prob.GraphNode.java:
package io.github.coderodde.prob;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
/**
* This class defines the graph node in a probabilistic graph.
*
* @author Rodion "rodde" Efremov
* @version 1.0.0 (Sep 16, 2025)
* @since 1.0.0 (Sep 16, 2025)
*/
public final class GraphNode {
private final int id;
private final Map<GraphNode, Double> neighbours = new HashMap<>();
public GraphNode(int id) {
this.id = id;
}
public void connectTo(GraphNode other, double probability) {
Objects.requireNonNull(other, "The other node is null");
checkProbability(probability);
neighbours.put(other, probability);
other.neighbours.put(this, probability);
}
public double getEdgeProbabilityTo(GraphNode neighbour) {
Objects.requireNonNull(neighbour, "The neighbour node is null");
if (!neighbours.containsKey(neighbour)) {
throw new IllegalArgumentException(
String.format(
"There is no edge between %s and %s",
this,
neighbour));
}
return neighbours.get(neighbour);
}
public Collection<GraphNode> getNeighbours() {
return Collections.unmodifiableSet(neighbours.keySet());
}
/**
* {@inheritDoc }
*/
@Override
public int hashCode() {
return id;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final GraphNode other = (GraphNode) obj;
return this.id == other.id;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[GraphNode id = ");
sb.append(id);
sb.append("]");
return sb.toString();
}
private static void checkProbability(double probability) {
if (Double.isNaN(probability)) {
throw new IllegalArgumentException("probability is NaN");
}
if (probability < 0.0) {
throw new IllegalArgumentException(
String.format(
"probability(%f) < 0.0",
probability));
}
if (probability > 1.0) {
throw new IllegalArgumentException(
String.format(
"probability(%f) > 1.0",
probability));
}
}
}
io.github.coderodde.prob.MostProbablePathFinder.java:
package io.github.coderodde.prob;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
/**
* This class contains a method that finds the most probable path in an
* undirected probability graph in which all the edge weights are probabilities
* within closed range {@code [0, 1]}.
*
* @author Rodion "rodde" Efremov
* @version 1.0.0 (Sep 16, 2025)
* @since 1.0.0 (Sep 16, 2025)
*/
public final class MostProbablePathFinder {
public Result findMostProbablePath(GraphNode source, GraphNode target) {
Objects.requireNonNull(source, "The source node is null");
Objects.requireNonNull(target, "The target node is null");
Map<GraphNode, Double> distanceMap = new HashMap<>();
Map<GraphNode, GraphNode> parentMap = new HashMap<>();
Queue<HeapEntry> openQueue = new PriorityQueue<>();
distanceMap.put(source, 0.0);
parentMap.put(source, null);
openQueue.add(new HeapEntry(source, 0.0));
while (!openQueue.isEmpty()) {
HeapEntry entry = openQueue.remove();
GraphNode node = entry.node;
if (node.equals(target)) {
List<GraphNode> mostProbablePath = tracebackPath(node,
parentMap);
double reliability = Math.exp(-distanceMap.get(target));
return new Result(mostProbablePath,
reliability);
}
double g = entry.g;
for (GraphNode neighbour : node.getNeighbours()) {
double weight = -Math.log(node.getEdgeProbabilityTo(neighbour));
double tentativeDistance = g + weight;
if (tentativeDistance <
distanceMap.getOrDefault(neighbour,
Double.POSITIVE_INFINITY)) {
distanceMap.put(neighbour, tentativeDistance);
parentMap.put(neighbour, node);
openQueue.add(new HeapEntry(neighbour, tentativeDistance));
}
}
}
// Target not reachable:
return new Result(List.of(), Double.NaN);
}
private static List<GraphNode>
tracebackPath(GraphNode target,
Map<GraphNode, GraphNode> parentMap) {
List<GraphNode> path = new ArrayList<>();
for (GraphNode node = target;
node != null;
node = parentMap.get(node)) {
path.add(node);
}
Collections.reverse(path);
return path;
}
private static final class HeapEntry implements Comparable<HeapEntry> {
GraphNode node;
double g;
HeapEntry(GraphNode node,
double g) {
this.node = node;
this.g = g;
}
@Override
public int compareTo(HeapEntry o) {
return Double.compare(g, o.g);
}
}
}
io.github.coderodde.prob.Result.java:
package io.github.coderodde.prob;
import java.util.List;
import java.util.Objects;
/**
* This class implements the result of finding a most probable path in instances
* of {@link MostProbablePathFinder}.
*
* @author Rodion "rodde" Efremov
* @version 1.0.0 (Sep 16, 2025)
* @since 1.0.0 (Sep 16, 2025)
*/
public final class Result {
private final List<GraphNode> path;
private final double probability;
public Result(List<GraphNode> path, double probability) {
this.path = Objects.requireNonNull(path, "The input path is null");
this.probability = probability;
}
public List<GraphNode> getPath() {
return path;
}
public double getProbability() {
return probability;
}
}
io.github.coderodde.prob.MostProbablePathFinderTest.java:
package io.github.coderodde.prob;
import org.junit.Test;
import static org.junit.Assert.*;
public class MostProbablePathFinderTest {
@Test
public void mostProbablePathIsLongest() {
GraphNode source = new GraphNode(0);
GraphNode target = new GraphNode(1);
GraphNode upper1 = new GraphNode(2);
GraphNode upper2 = new GraphNode(3);
GraphNode middle = new GraphNode(4);
GraphNode lower = new GraphNode(5);
// Build the most probable path:
source.connectTo(upper1, 0.99);
upper1.connectTo(upper2, 0.97);
upper2.connectTo(target, 0.95);
// Build the middle (vertically) that is two edges long but not as
// probable as the above path:
source.connectTo(middle, 0.8);
middle.connectTo(target, 0.7);
// Build the lower suboptimal path:
source.connectTo(lower, 0.1);
lower.connectTo(target, 0.4);
Result result =
new MostProbablePathFinder()
.findMostProbablePath(source,
target);
assertEquals(result.getProbability(), 0.99 * 0.97 * 0.95, 0.01);
}
@Test
public void noResultOnUnprobablePaths() {
GraphNode source = new GraphNode(0);
GraphNode target = new GraphNode(1);
GraphNode upper = new GraphNode(2);
GraphNode lower = new GraphNode(3);
source.connectTo(upper, 0.0);
upper.connectTo(target, 1.0);
source.connectTo(lower, 0.5);
lower.connectTo(target, 0.0);
Result result =
new MostProbablePathFinder()
.findMostProbablePath(source,
target);
assertTrue(result.getPath().isEmpty());
assertTrue(Double.isNaN(result.getProbability()));
}
}
Critique request
As always, I am eager to hear any constructive critique on my (re)attempt.
