Просто интересно, при задании графа матрицей смежности, за бесконечность машинную кокое число брать?
я так подумал дожно хватить число равное самому большому весу ребра, не равному бесконечности, умноженнона 2 напрмиер (ну а если еще точнее, то сумма двух наибольших небесконечных ребер(весов)).
P.S. Меня конечно интересует самое минамальное число для использованияв качестве машинной бесконечности.
сумма двух наибольших небесконечных ребер, мне кажется точнее всего.
например, на матрице
0 1 I I
1 0 2 I
I 2 0 3
I I 3 0
где I - бесконечность, вершина 1 соединена с 2 ребром веса 1, 2 с 3 весом 2, 3 с 4 весом 3 ваш алгоритм заменит I на 5 и кратчайший путь будет 5 (а должен быть 6).
для поиска минимального пути за бесконечность вполне пойдет сумма всех положительных ребер. если запрещены ребра отрицательного веса, то можно заменить бесконечность на -1 и обрабатывать отдельно.
да, точно, спасибо!