# 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?

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())) {
dfs(vertex.getKey(),visited,currentTime + vertex.getValue());
visited.pop();
}
}
}

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