Déjà avant de regarder plus en détail si ta matrice n'est pas carré il faut que tu la transforme en matrice carré en mettant à l'infini les cases rajoutées. Sinon ça ne peut pas marcher puisque l'algorithme à besoin d'une matrice carré.

Tu peux utiliser un tableau de String :
private static final chiffres={"M","CM",..};
et c'est ce tableau que tu parcours. Le string te permet d'accéder à la valeur de l'élément grâce à la hashtable.
Je pense qu'au niveau complexité c'est mieux.

On pourrait aussi parcourir le nombre de droite à gauche mais comme j'y vois je ne pense pas que ce serait mieux.

Tu ferais mieux d'utiliser une Hashtable plutôt que des ArrayList ce serait plus performant. Tu dois d'ailleur pouvoir la rendre static et final.
private static final Hashtable<String, Integer> chiffres_romain = new Hashtable<String, Integer>();

les ? n'empèchait pas la comprension, ce n'etait qu'un nom de variable. Je trouve que l'utilisation de la lettre C et l'appellation de la fonction cout C sans paranthèse est plus génante pour la comprehension.

Donc si je comprend bien en mettant des ? dans la diagonale on retombe sur le problème du voyageur de commerce.(VDC ou TSP http://en.wikipedia.org/wiki/Travelling_salesman_problem)

Merci.

J'aimerais juste avoir un ou deux exemple(s) concret(s) de l'utilisation de l'algorithme.

Merci.

PS : La note que je met ne correspond à rien puisque je n'ai pas regardé les sources.
<a href="http://en.wikipedia.org/wiki/Hungarian_algorithm">Un peu plus d'information sur l'algo<a> (en anglais)