Средняя длина пути сетевого графа?

Question

У меня есть этот сетевой график:

Я создал матрицу расстояний на основе каждой вершины:

Теперь я хочу найти «среднюю длину пути» приведенного выше сетевого графа, но в определении указано «1017 *» средняя длинакратчайший путь между любыми двумя вершинами ".Я не мог обдумать это определение и подумал, может ли кто-нибудь помочь мне в этом.

Answer 1

«- кратчайший путь между двумя вершинами» относится к минимальному количеству шагов или наименьшей возможной сумме весов ребер (только 1 для этого случая невзвешенного графа) от местоположения до вершины назначения.

Среднее значение рассчитывается по всем возможным путям, таким как A - B и B - A, однако мы не рассматриваем A к A, поскольку график не иллюстрирует какие-либо рекурсивные пути.

Поэтому вычислять среднее значение посуммирование всех значений пути из вашей таблицы и деление на количество путей (исключая рекурсивные пути, такие как от A до A).

41/30 = 1,4 (округлено от 1,36)