Уже 2 дня ломаю голову. Вздрагиваю при взглюде на любую карту. Перерыл теорию графиков. Нашел множество алгоритмов на нахождение коротчайшего пути в графике без циклов. А с циклами вооще неодного. Может быть кто нибудь сталкивался с похожей задачей. Или знает где найти информацию. Предложениям и идеям буду рад.
Задача выглядит примерно так.
Дано= Ненаправленный циглический график. Тоесть растояние от А на А не всегда =0 и от А на Б может быть несколько возможных путей.
Задача= Найти длинейший путь. Так что бы кажое соединение было только один раз.(Как бы нарисовать неотрывая руки ) К примеру если есть A->A>0 тогда выбирать этот путь. И если есть несколько возможностей А->Б то выбирать длинейший.
Структура данных выглядит так:
Knote{ int ID}
Kante {Knote a , Knote b , int laenge}
Graph{ArrayList <Kante> kanten }

Графов, а не графиков. Кратчайший путь между двумя узлами находится с помощью алгоритма Дейкстры - http://de.wikipedia.org/wiki/Dijkstra-Algorithmus. Странно, что ты его не нашёл, этот алгоритм в теории графов дают обычно самым первым.
PS Наличие/отсутствие циклов этот алгоритм вообще мало волнует.
PPS Тут и программировать ничего не надо, берёшь буст и считаешь. Вот готовый пример - http://www.boost.org/libs/graph/example/dijkstra-example.cpp
PPPS ОК, забудь. Ты меня сбил с толку неточной постановкой вопроса.

Кратчайший путь между двумя узлами находится с помощью алгоритма Дейкстры
он же про *длинейший путь* молвит.

А, сейчас дошло. Он меня сбил своими рассуждениями о кратчайшем пути.

По-моему метод ветвей и границ должен сработать. Пишем минус бесконечность в несуществующие рёбра и ищем максимум.

Помоему ты меня неправильно понял или я неправильно понял метод метода ветвей и границ. Помоему этот метод не пойдет. Я прикрипил jpg-шку. с примером. Стрелки во внимание не принимать.
Алгоритм должен выдать AB-BC-СD-DB-BE-EF-FG-GH-HI-IJ-JL-LF-FM-MN . Если предположить что длина каждого соединения одинакова. Причем без разницы в каком порядке. Или хотябы AB.laenge + BC.laenge +......+ MN.laenge.

Смотри по ключевым словам Задача Комивояжера.

Комивояжор должен проехать все города по минимальному пути заезжая в каждый город один раз. Мне же проезжать все городе не надо да и в города заезжать я могу много раз. А вот проезжать по одному и томожу пути я могу только один раз.

Ну тогда придется комбинировать что-то типа Волны (см. трассировка печатных плат, метод волны) и перебора.
И насколько точно надо посчитать? Обычно можно не считать, а обойтись приблизительной верхней оценкой.

Надо точно.

Помоему можно модифицировать Дейкстру
перебираем все маршруты помечая посещенные узлы, попутно запоминая максимальное расстояния до узла. (C#)

// Program.cs
using System;
using System.Collections.Generic;
using System.Text;
namespace LongestWay {
  class Node {
    public List<Edge> Edges = new List<Edge>();
    public bool Visited = false;
    public double MaxDistance = 0d;
    public List<Node> LongestWay;
    public void WalkIn(double distance, Stack<Nodes> way) {
      if (Visited) return;
      Visited = true;
      if (distance > MaxDistance) {
        MaxDistance = distance;
        LongestWay = new List<Node>(way);
      }
      way.Push(this);
      foreach (Edge edge in Edges) {
        edge.Node.WalkIn(distance + edge.Length);
      }
      way.Pop();
      Visited = false;
    }
    public override string ToString() {
      // dump results
      return string.Format("MaxDistance: {0}",MaxDistance);
    }
  }
  class Edge {
    public double Length;
    public Node Node;
  }
  class Program {
    static void Main(string[] args) {
      List<Node> nodes =
 new List<Node>();
      Node start = new Node();
      /* hier fill nodes, edges and set start node */
      foreach (Node node in nodes) {
        node.MaxDistance = 0d;
        node.Visited = false;
      }
      start.WalkIn(0d, new Stack<Nodes>());
      foreach (Node node in nodes)
        Console.WriteLine(node);
    }
  }
}

Есть способ вычисления всех "уникальных" путей в системе. Потом можно быбрать самый длинный.
S. Schuster and C. Hilgetag: On Elementary Flux Modes in Biochemical Reaction Systems at Steady State, Journal of Biological Systems 2, 1994, 165-182.
---
Хорошо когда собака - друг, но плохо, когда друг - собака.

Не получится. Если помечать узлы тогда циклы не будут считатся. А если помечать соединения тогда путь не всегда получается длинейшим, если к примеру первым был выбран путь который короче. Если ничего не помечать тогда бегаем по кругу.

Действительно, ответ немного не на ту задачу. Но я не понял в чем проблема если помечать соединения и в каждом узле перебирать все соединения которые до сих пор не помечены?
Рекурсивно переберем все возможные пути.
Что касается путей само на себя (A->A) то их просто добавлять к общему пути при первом посещении узла А. В принципе перебор их тоже посчитает, но так быстрее будет.

Алгоритм почти работает но:
Правильный результат можно получить только если стартовать с точки A или N.
если начать в точке N тогды на узле F три возможности дальнейшего пути. На G на L и на E. Если алгоритм выбирит в первую очередь L или G тогда все нормально. но если пойдет на E в первую очередь тогды все точки от E начиная влево будут иметь не максимальное растояние. Так как цикл FGHIJLF не учитывается.
Если начать с A таже история.

Все работает. если не останавливать перебор после того как дошли до заданной точки алгоритм найдет и короткий путь и пути содержащие циклы FGHIJLF и FLJIHGF.
Суть в том что ищутся все возможные пути.
Что мне код написать, что бы понятно стало?

Я хренею дарагая ридакцея.
1. Заменяешь расстояния x -> 1/x (т.е. вместо 2 ставишь 1/2=0.5,
вместо 4 имеем 1/4=0.25 и т.д.)
2. Находишь любым из известных способом кратчайший путь
(кратчайший путь для обратных расстояний и будет длиннейшим для оригинальных расстояний)

1. Заменяешь расстояния x -> 1/x (т.е. вместо 2 ставишь 1/2=0.5,
вместо 4 имеем 1/4=0.25 и т.д.)
из того что 1/a + 1/b > 1/c + 1/d не следует что с+d > a + b
пример 0.5 + 0.5 < 0.1 + 1 и 1/0.5 + 1/0.5 < 1/0.1 + 1/1
так что не пойдет

Ой
а жаль

кажися кроме как перебором не решается,
возможно упрошение типа: отбросить тупиковые ветви
(ветви, узлы которых не являются началом и концом "путешествия" и у каждого не более 2 связей)
хотя это еше как делать перебор, может это упрошние и не нужно вовсе