行列ベースのベルマンフォード法

Matlab,Octaveによる実装

A:コスト隣接行列
d:各頂点への最短距離

・メインコードから呼び出すminplus関数の定義

function x = minplus(d,A) 
	[M,N] = size(A);
	for i = [1:N]
		x(i) = min(A(:,i)' + d);
	endfor
endfunction

※以下の記法は通常の積をminplusとして置き換えて考える。
dn = d0*A^nを二通りのパターンで更新する。

1. dn = (d0*A^(n-1)) * Aとして(d0*A^(n-1)) を更新していくコード

function algebraicbellmanford(A,s)
	[M,N] = size(A); 
	for i = [1:N]
		d(i) = inf;
	endfor
	d(s) = 0;
	for j = [1:N + 1]
		d = minplus(d,A);
	endfor
	if all(d == minplus(d,A)) == 0
		"A negative-weight cycle exists" 
	endif
endfunction

2. A^nを先に更新するコード
A^nは全点対最短路の隣接行列が得られる。ワーシャルフロイドっぽくなる
三重ループ回さなくても、行列演算でもっと短くかけそう。

function algebraicsquarbellmanford(A,s) 
	[M,N] = size(A);
	for i = [1:N]	
		d(i) = inf;
	endfor
	d(s) = 0;
	for k = [1:N]
		for i = [1:N]
			for j = [1:N]
				A(i,j) = minplus(A(i,:),A(:,j));
			endfor
		endfor
	endfor
	d = minplus(d,A);
endfunction