Bellman-Ford i Java

Jisses, äntligen fick jag till algoritmen. Faktum är  ju att den är busenkel, och förbaskat logisk, men under förra perioden fastnade jag ordentligt när jag skulle implementera den. Jag antar att jag missuppfattat källorna för kostnaderna, och använt fel och inaktuell data i beräkningarna av de nya vektorerna. Man fastnar lätt i fel tänk, och tror att man gör saker som man inte gör. Nyligen höll jag på att fastna i tänket att jag för att få reda på bästa vägen till en nod rimligen måste gå via en annan nod, och därmed behöver jag först ta reda på vektorn till den noden. För att göra det behöver jag gå via en nod för att hitta bästa vägen dit…

Jag missuppfattade återigen vilka värden jag skulle använda. Vi är inte ute efter vektorn till grannen, utan den direkta kostnaden – raka spåret. Sen ska vi kolla vad denna granne har för vektor till slutnoden. Addera, krymp ner så långt det går, och vips har vi vår egen vektor till slutnoden. Jag tjänade utan tvekan på att låta uppgiften vila ett tag, så att logiska missöden som denna självdör.

private boolean bellmanFord() {
	/*
	 * Find the best way to node, by going through each neighbor.
	 * 
	 * B-F equation says dx(y) = minv {c(x,v) + dv(y) }
	 * where c(x,v) is the direct link cost from x to v
	 * and dv(y) is the neighbors(v) vector to y.
	 * 
	 * We use these values and add them together, and try
         * to lower this value as much as possible.
	 * The result will be our distance vector.
	 */
	boolean updated = false;
	for (int node = 0; node < graph.length; node++) {
		int cost = RouterSimulator.INFINITY;
		int costToNode = RouterSimulator.INFINITY;
		for (int neighbor: neighbors) {
			int costToNeighbor = directs[neighbor];
			int costFromNeighbor = graph[neighbor][node];
			costToNode = costToNeighbor + costFromNeighbor;
			if (node == myID) {
				// Ensure the cost to myself is 0
				cost = 0;
			}
			if (costToNode < cost) {
				cost = costToNode;
			}
		}
		if (graph[myID][node] != cost) {
			graph[myID][node] = cost;
			updated = true;
		}
	}
	return updated;
}

Svårare än så är det inte!