New answers tagged

1

You can optimize a bit by make it possible to step out of the first outer loop if the inner foreach-loop doesn't make any changes to dist in one iteration. Wouldn't it be possible to test for maxWait whenever you update dist[v] in the foreach-loop: { dist[v] = dist[u] + w; maxWait = Math.Max(maxWait, dist[v]); } This may og may not be an ...


2

Multi-statement lines This: stack = []; result = [] lowlinks = {}; index = {} # ... if successor == node: break is generally discouraged; just use two lines. snake_case This: lowlinks is usually spelled out, i.e. low_links. Bare except try: successors = graph[node] except: successors = [] has an except statement that's too ...


1

Be explicit about the data structure you're using, and the assumptions. For example, a comment like this would be helpful for any future readers(including yourself): "We represent a graph as adjacency list stored in a Python dictionary. The adjacency list can contain nodes that are not present in the keys of the dictionary, and they should be treated as ...


1

The answers that have been posted (including the accepted answer) are wrong because they don't explore the vertex completely before moving onto the next vertex. For the below adjacency matrix test_graph = { 1: [2, 4, 5], 2: [3, 6, 7], 3: [], 4: [], 5: [], 6: [], 7: [] } The output should be 1, 2, 4, 5, 7, 6, 3, or 1, 5, 4, 2, 3, ...


-1

Works on a number of cases I've tested with: def dfs_iterative(graph, start_vertex): visited = set() traversal = [] stack = [start_vertex] while stack: vertex = stack.pop() if vertex not in visited: visited.add(vertex) traversal.append(vertex) stack.extend(reversed(graph[vertex])) # add ...


0

Two small, related points public void calculateShortedPath(int source) Seems like it should be calculateShortestPath (not Shorted). At the moment the method returns void and is responsible for both calculating the path and printing it out. Consider changing it to return the shortest path instead, so that the caller can decide what it wants to do with ...


3

Hey, I think you have pretty nice code there already. Anyways, I have some suggestions: Formatting This looks pretty good already so please don't take the points to seriously. Mostly it's my personal preferences. I don't like breaking variable definitions like so: private HashMap<GraphVertex, LinkedList<WeightedEdge>> ...


0

I'm by no means a java programmer, just some things I noticed. GraphVertex.equals This method is messy to say the least. The number of return in this method mixed with if statements with no brackets makes it hard to read. And, it looks like you only want to check one condition, anything else other than that would result in a false return. Now, you only ...


0

My computer theory classes have been a couple of decades ago, so I may be wrong, but you seem to be confusing the terms "node", "vertex", "edge" and some more. Unless I'm mistaken "node" and "vertex" are the same thing, so I'd suggest to use one or the other, but not both. You also seem to sometimes call the value assigned to a vertex "node". Use a ...


1

The advice I think most important: stick to the Style Guide for Python Code It helps everyone - including yourself - read your code. Naming: name things for what they can/will be used for, their raison d'être. For example, the class featuring push(), rem(), and _properPlace() is not used to be open or open something. It looks a priority queue with ...


Top 50 recent answers are included