File Exchange

## hamiltonian(Graph, Source, Destination)

version 1.0.0.0 (3.13 KB) by Pramit Biswas

### Pramit Biswas (view profile)

This MATLAB function can be used to find Hamiltonian Path or Cycle

Updated 28 Jun 2015

This MATLAB function c% Let us create the following graph
(1)--(2)--(3)-------(4)
| / \ | |
| / \ | |
| / \ | |
(5)-------(6) |
| |
| |
| |
(7)-------------------(8)

g=[0 1 0 0 1 0 0 0;
1 0 1 0 1 1 0 0;
0 1 0 1 0 1 0 0;
0 0 1 0 0 0 0 1;
1 1 0 0 0 1 1 0;
0 1 1 0 1 0 0 0;
0 0 0 0 1 0 0 1;
0 0 0 1 0 0 1 0]
s=5; % Source
d=1; % Destination
P = hamiltonianPath(g,s,d);

P will be an array mentioning the path/cycle, if path/cycle found; or a

#Note: This code can be used for finding Hamiltonian cycle also. For
that, make sure Source and Destination are same.

### Cite As

Pramit Biswas (2020). hamiltonian(Graph, Source, Destination) (https://www.mathworks.com/matlabcentral/fileexchange/51610-hamiltonian-graph-source-destination), MATLAB Central File Exchange. Retrieved .

Pramit Biswas

### Pramit Biswas (view profile)

@pkc yes this code only provides a single Hamiltonian path. Thanks for correcting. @dedeff sorry, my mistake.

pkc

### pkc (view profile)

@ Pramit Biswas, I think dedeff was looking for multiple Hamiltonian paths for each given source and destination pair. Correct me if I'm wrong, but doesn't your code find only one Hamiltonian path for each given source and destination pair?

Pramit Biswas

dedeff

### dedeff (view profile)

Hi, is it possible to find all the hamiltonian Path from a source to a destination?

Pramit Biswas

### Pramit Biswas (view profile)

@zein what is the exact error?

Pramit Biswas

zein smak

### zein smak (view profile)

after i download this file, open with matlab. there is an error, why?

Error in hamiltonian (line 39)
if ~isreal(Graph)

Pramit Biswas

### Pramit Biswas (view profile)

Need to create simple connection matrix. Means, if node 1 is connected to node 2 then g(1,2)=1 and if node 1 is not connected to node 3 then g(1,3)=0, and so on.

Pramit Biswas

### Pramit Biswas (view profile)

@gustav: simple.
just make two nested for loop, and call this function to get all the path.

Remember: it can take a long time for larger graph

Gustavo Ulloa

Gustavo Ulloa

### Gustavo Ulloa (view profile)

Do you known how to find all the hamiltonian paths? if there is more than one

kalohr

### kalohr (view profile)

thanks for the contribution

could you be kind enough as to explain how g represents the graph above ?

##### MATLAB Release Compatibility
Created with R10
Compatible with any release
##### Platform Compatibility
Windows macOS Linux