Помоему можно модифицировать Дейкстру
перебираем все маршруты помечая посещенные узлы, попутно запоминая максимальное расстояния до узла. (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);
    }
  }
}