Граф (определение бесконечности). Опции

[Altair]

Просто интересно, при задании графа матрицей смежности, за бесконечность машинную кокое число брать?
я так подумал дожно хватить число равное самому большому весу ребра, не равному бесконечности, умноженнона 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 и обрабатывать отдельно.

[Altair]

да, точно, спасибо!