# Command for finding maximum weight Hamiltonian path between two vertices

A Hamiltonian path is a graph path between two vertices of a graph that visits each vertex exactly once. Finding a single Hamiltonian path of a graph $$g$$ is implemented in the Wolfram Language as FindHamiltonianPath[g]

What command could be used to find the Hamiltonian path with maximum path weight between the starting vertex $$s$$ and the terminating vertex $$t$$ in the following edge labeled graph?

• FindShortestTour can also be used as sp = Last@ FindShortestTour[Graph[edges, EdgeWeight -> (1 - edgeweights)], s, t] Commented Mar 25, 2021 at 14:15

edges = {1 <-> 2, 1 <-> 3, 1 <-> 5, 2 <-> 3, 2 <-> 4, 2 <-> 5,
3 <-> 4, 3 <-> 6, 3 <-> 7, 4 <-> 5, 4 <-> 6, 5 <-> 6, 5 <-> 7,
6 <-> 7};
edgeweights = {.5, .5, .7, .3, .6, .7, .6, .4, .8, .7, .6, .7, .8, .8};

graph = Graph[Range[7], edges,
EdgeWeight -> edgeweights,
EdgeLabels -> Placed["EdgeWeight", Center],
EdgeLabelStyle -> 16,
VertexLabels -> Placed["Name", Center],
VertexSize -> Large,
ImageSize -> Large,
GraphLayout -> {"LayeredDigraphEmbedding", "Orientation" -> Left}]


{s, t} = {1, 7};


To find the Hamiltonian path with maximum path weight, we construct a new graph using 1 - edgeweights as the setting for EdgeWeight and use FindHamiltonianPath:

hp = FindHamiltonianPath[Graph[edges, EdgeWeight -> (1 - edgeweights)], s, t]

{1, 3, 4, 2, 5, 6, 7}

HighlightGraph[graph, PathGraph[hp], GraphHighlightStyle -> "Thick"]


• Does FindHamiltonianPath take weights into account at all? The documentation does not suggest so, but then the Graph documentation is often incomplete. Commented Mar 24, 2021 at 12:11
• I just tried this: g = CompleteGraph[4, EdgeWeight -> Reverse@{1, 2, 3, 4, 5, 6}, EdgeLabels -> "EdgeWeight", VertexLabels -> Automatic] then FindHamiltonianPath[g]. The result is the same, regardless of whether I remove Reverse or not. This confirms that FindHamiltonianPath does not consider weights. Commented Mar 24, 2021 at 12:13
• @Szabolcs, i tried the example el = {1 <-> 2, 1<-> 3, 1 <-> 4, 2 <->] 3, 3<-> 4}; ew = {0.5, a, 0.5, 0.5, 0.5}; Graph[el, EdgeWeight -> ew, EdgeLabels -> "EdgeWeight", VertexLabels -> Placed["Name", Center]]. With a=1 , FindHamiltonianPath gives {4, 3, 2, 1} and with a=.1 it gives {4, 3, 1, 2} which led me to assume "the smallest total length" meant smallest total weight for weighted graphs. But there is no explicit mention of what total length actually means.
– kglr
Commented Mar 24, 2021 at 12:28
• So it does take weights into account in some way. But in my example from the comment above, I get {1,2,3,4} as the output. That's a total weight of 10. {1,4,3,2} would be a total weight of 8, i.e. lower. I am using M12.2. Do you get the same result as me? What am I missing? Commented Mar 24, 2021 at 12:37
• I get the same result {1,2,3,4} in both version 11.2.0 and 12.2 (wolfram cloud).
– kglr
Commented Mar 24, 2021 at 12:50