Если график не направленный, набор кратчайших путей от A до B (S_{ab}) совпадает с набором кратчайших путей от B до A (S_{ba}). Вы можете доказать это противоречием.
Предположим, это не так. Таким образом, существует по крайней мере один путь P от B до A, которого нет в S_{ab}. Поскольку график не направленный, существует такой же путь от A до B. Если длина пути больше, чем весь путь в S_{ab}, то это не самый короткий путь от B до A, так как вы можете вернуться от B до A с одним из путей в кратчайшем путив S_{ab}.
Кроме того, если длина P меньше длины путей в S_{ab}, то мы можем перейти от A до B с меньшими затратами, чем всепуть в S_{ab}. Следовательно, P должно быть в S_{ab} по определению множества. Но это противоречит предположению. Следовательно, это невозможно.