1
$\begingroup$

I have an undirected weighted graph like this one

enter image description here

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?

$\endgroup$

migrated from stackoverflow.com Jun 5 '18 at 14:15

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

-2
$\begingroup$

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())) {
            visited.add(vertex.getKey());
            dfs(vertex.getKey(),visited,currentTime + vertex.getValue());
            visited.pop();
        }
    }
}
$\endgroup$
  • $\begingroup$ TSP also visits each vertex exactly once. $\endgroup$ – xskxzr Jun 8 '18 at 19:10
  • $\begingroup$ What is entrySet? What is vertex.getValue()? Could you please describe your algorithm by pseudo-code? $\endgroup$ – xskxzr Jun 8 '18 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy