Можно ли из графа убрать одно ребро, чтобы расстояние между двумя любыми вершинами не превышало N

Дан граф в виде списока из
Название_города1 Координата1 Координата2
Название_города2 Координата1 Координата2
...
И матрица смежности.
Задание состоит в том, чтобы проверить, можно ли убрать одно ребро, чтобы расстояние между двумя любыми городами не превышало N (вводится к клавиатуры). Есть алгоритм, который решает это напрямую: перебирает все дороги, убирает их по одной и проверяет на верность условия.

public void AbleToCut(int n)
{
     int x;
     for (int i = 0; i < graph.Size - 1; i++)
     {
         for (int j = i+1 ; j  < graph.Size; j++)
         {
             if (graph[i, j] != 0)
             {
                 Console.ForegroundColor = ConsoleColor.Blue;
                 Console.WriteLine("Перекрываем дорогу между {0} и {1}", cities[i], сities[j]);
                 Console.ResetColor();

                 Node tmpGraph = graph;
                 x = tmpGraph[i, j];
                 tmpGraph[i, j] = 0;
                 tmpGraph[j, i] = 0;

                 long[,] res = tmpGraph.Floyd(out int[,] p);
                 bool flag = true;
                 for (int k = 0; k < res.GetLength(0) - 1; k++)
                 {
                     for (int m = k + 1; m < res.GetLength(0); m++)
                     {
                         if (res[k, m] > n && res[k, m] < int.MaxValue)
                         {  
                             Console.WriteLine("Расстояние между {0} и {1} превышает N ({2})", cities[k], cities[m], res[k,m]);
                             flag = false;
                             break;
                         }
                     }
                     if (!flag)
                         break;
                 }
                 if (flag)
                 {
                     Console.ForegroundColor = ConsoleColor.Green;
                     Console.WriteLine("Можно перекрыть дорогу между городами {0} и {1}", cities[i], cities[j]);
                     Console.ResetColor();
                 }
                 tmpGraph[i, j] = x;
                 tmpGraph[j, i] = x;
            }
        }
    }
}

Алгоритм Флойда, где array - матрица смежности состоящая из нулей, если дороги нет, или расстояния между городами:

public long[,] Floyd(out int[,] p)
{
    int i, j, k;
    //создаем массивы р и а
    long[,] a = new long[Size, Size];
    p = new int[Size, Size];
    for (i = 0; i < Size; i++)
    {
        for (j = 0; j < Size; j++)
        {
            if (i == j)
            {
                a[i, j] = 0;
            }
            else
            {
                if (array[i, j] == 0)
                {
                    a[i, j] = int.MaxValue;
                }
                else
                {
                    a[i, j] = array[i, j];
                }
            }
            p[i, j] = -1;
        }
    }
    //осуществляем поиск кратчайших путей
    for (k = 0; k < Size; k++)
    {
        for (i = 0; i < Size; i++)
        {
            for (j = 0; j < Size; j++)
            {
                long distance = a[i, k] + a[k, j];
                if (a[i, j] > distance)
                {
                    a[i, j] = distance;
                    p[i, j] = k;
                }
            }
        }
    }
    return a;//в качестве результата возвращаем массив кратчайших путей между
} //всеми парами вершин

Нужно придумать, как это сделать оптимальнее, без перебора