2
$\begingroup$

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?

enter image description here

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

1 Answer 1

3
$\begingroup$
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}]

enter image description here

{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"]

enter image description here

$\endgroup$
10
  • 1
    $\begingroup$ Does FindHamiltonianPath take weights into account at all? The documentation does not suggest so, but then the Graph documentation is often incomplete. $\endgroup$
    – Szabolcs
    Mar 24, 2021 at 12:11
  • $\begingroup$ 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. $\endgroup$
    – Szabolcs
    Mar 24, 2021 at 12:13
  • $\begingroup$ @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. $\endgroup$
    – kglr
    Mar 24, 2021 at 12:28
  • $\begingroup$ 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? $\endgroup$
    – Szabolcs
    Mar 24, 2021 at 12:37
  • $\begingroup$ I get the same result {1,2,3,4} in both version 11.2.0 and 12.2 (wolfram cloud). $\endgroup$
    – kglr
    Mar 24, 2021 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.