# Find shortest path in undirected graph that goes through all vertices and returns to starting vertex

I have an undirected weighted graph like this one My task is to find the fastest path (with least weight) that goes from specified vertex goes through all vertices and returns to the starting vertex without repeating a vertex.

Graph
1 3 time 5
3 2 time 5
2 4 time 5
4 1 time 5
4 3 time 4
1 2 time 5

Starting vertex 3
Path 1: 3->1->4->2->3
Path 2: 3->2->1->4->3
Time 1 and 2: 5+5+5+5=20

Path 3: 3->1->2->4->3
Path 4: 3->4->2->1->3
Time 3 and 4: 5+5+5+4=19 -> fastest


Is there a fastest way than DFS to solve the problem?

## migrated from stackoverflow.comJun 5 '18 at 14:15

This question came from our site for professional and enthusiast programmers.

Travelling salesman problem looks almost the same but I can't repeat a visited vertex.

Going from vertex 3 to vertex 5 I can't do that 3 -> 2 -> 3 -> 1 -> 3-> 4 -> 3

A solution is: 3->1->2->4->3

That's my function:

private static List<HashMap<Integer,Integer>> graph = new ArrayList<>();

public static void dfs(int currentVertex,Stack<Integer> visited,long currentTime) {
if(visited.size() == graph.size()-1) {
if(!graph.get(currentVertex).containsKey(targetVertex)) {
return;
}

currentTime += graph.get(currentVertex).get(targetVertex);
if(currentTime < fastestTime) {
fastestTime = currentTime;
}
return;
}

for (Map.Entry<Integer,Integer> vertex: graph.get(currentVertex).entrySet()) {
if(!visited.contains(vertex.getKey())) {

• What is entrySet? What is vertex.getValue()? Could you please describe your algorithm by pseudo-code? – xskxzr Jun 8 '18 at 19:16