Как обсуждалось в комментариях к вопросу, не очень ясно, что именно представляет собой установка epitaph , и по какой-то причине он / она, кажется, не желает уточнить. Но давайте предположим, что «граф» на самом деле просто представлен матрицей расстояний (которая может быть тем, что предполагается показать путаницей чисел и X в вопросе), с фактическим числовым расстоянием для каждой пары вершин.
В этом случае здесь не происходит ничего очень графического; есть край для каждой пары без исключения вершин; и все, что мы можем сделать, это перечислить каждую тройку вершин.
Для каждого набора из трех вершин a, b, c нам нужно проверить, что d (a, b) <= d (a, c) + d (c, b) и что d (a, c) <= d (a, b) + d (b, c), и что d (b, c) <= d (b, a) + d (a, c). Итак, давайте сделаем это. Ниже приводится псевдокод, потому что, если я попытаюсь написать его на PHP (который я использую как можно реже), я сделаю ошибки. </p>
for i from 0 to n_vertices-3
for j from i+1 to n_vertices-2
for k from j+1 to n_vertices-1
# now i,j,k are three distinct vertices, and every set of three vertices
# will occur once as we run through the loops.
a = distances[i,j]
b = distances[i,k]
c = distances[j,k]
if a>b+c or b>a+c or c>a+b
triangle inequality is violated; complain
Если ваш график представлен не в виде матрицы расстояний, а в том случае, если множество ребер может не существовать, вам нужно сделать что-то другое.
(Примечание: если ваш график должен удовлетворять неравенству треугольника, то, возможно, в нем не должно быть пропущено ни одного ребра, если он фактически не отсоединен. Это зависит от того, должны ли расстояния быть «кратчайшим расстоянием от х до у» «(в этом случае, если неравенство треугольника терпит неудачу, то что-то нарушается, и в связном графе не должно быть отсутствующих ребер) или« расстояние прямого пути от x до y »(в этом случае, если неравенство треугольника терпит неудачу, это просто указывает что якобы прямой путь не стоит использовать).)