Das kann so nicht funktionieren, denn wenn Du weder Start noch Endpunkt hast, kannst Du keinen Weg innerhalb Deines Graphen definieren: Weg (Graphentheorie) ? Wikipedia
Ob ich nun formal die Knoten mit in die Menge der Kanten mitaufnehme ist dabei unerheblich. Generell wäre die Frage, ob es wirklich "der" längste Weg sein muss, denn hierbei wirst Du nur die Möglichkeit haben, alle Wege zu prüfen, was zur NP-Vollständigkeit führt.
Zweitens was ist, wenn Du mehrere Wege hast, die gleich lang sind? Wie sehen die Gewichte der Kanten aus, nimmst Du pauschal mit 1 an oder wichtest Du ggf? Was ist mit redundanten Wegen / Kreisen / Zyklen?
Ansätze wäre über den Spannbaum ? Wikipedia, der zunächst einmal alle Knoten in einem Graph berührt, damit Du keine redundanten Pfade hast.
Weiterhin wäre z.B. eine Möglichkeit nach dem Bellman-Algorithmus ? Wikipedia dem aktuellen Knoten die längsten/kürzesten Kante nimmst. Damit solltest Du z.B. eine gute Näherung erreichen.
Letztendlich würde ich das Problem aber in das Problem des Handlungsreisenden ? Wikipedia (TSP) einordnen und entsprechend dort die Algorithmen verwenden