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-&gt;1-&gt;4-&gt;2-&gt;3
Path 2: 3-&gt;2-&gt;1-&gt;4-&gt;3  
Time 1 and 2: 5+5+5+5=20

Path 3: 3-&gt;1-&gt;2-&gt;4-&gt;3     
Path 4: 3-&gt;4-&gt;2-&gt;1-&gt;3  
Time 3 and 4: 5+5+5+4=19 -&gt; 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&lt;HashMap&lt;Integer,Integer&gt;&gt; graph = new ArrayList&lt;&gt;();


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

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

    for (Map.Entry&lt;Integer,Integer&gt; vertex: graph.get(currentVertex).entrySet()) {
        if(!visited.contains(vertex.getKey())) {
            visited.add(vertex.getKey());
            dfs(vertex.getKey(),visited,currentTime + vertex.getValue());
            visited.pop();
        }
    }
}