Weight-maximizing (weighted vertices) path algorithm

algorithmsgraph

I am looking for description (name of algorithm, code, pseudocode, etc.) that can help me frame this problem and find the appropriate recursion and the most efficient solution.

Problem:
Given a graph with weighted nodes and a starting node, I want to generate a weight-ordered list of nodes that are lying on a path that starts at the starting node and then proceeds by jumping to the next adjacent unvisited highest-value node, then to the next etc. until it can no longer continue (e.g. no adjacent nodes, no unvisited adjacent nodes, or all nodes were visited already once).

Am I correctly assuming that this is a variation on the traveling salesman problem? Any suggestions or pointers would be greatly appreciated. Algorithms just aren't my area of expertise…

Update from comments: This is not a homework question. … There's actually years of empirical research behind simply being able to frame seemingly random mammalian behavior as an algorithmic problem. … Without tackling these group dynamics algorithmically I will not be able to expand testing beyond my initial sample and unfortunately, regression analysis just won't do the trick.

Best Answer

If I understand correctly then no, this isn't a variation on the TSP. It's a pretty straight forward greedy algorithm.

Here is some psuedocode:

List visited = {}

Main(Node startNode)
  FindPath(startNode)
  sort(visited)

FindPath(Node node)
  visited.addNode(node)
  neighbours = node.getAdjactentNodes()
  neighbours.subtract(visited)
  if(neighbours.isEmpty())
    // all adjacted nodes are visited
    return
  else
    sort(neighbours)
    FindPath(neighbours.First())
  end if

So -- what's happening here?

We are creating a list to hold all the nodes we've visited on our journey.

In FindPath: We then visit the node, we add it to the list of visited nodes and ask it for a list of neighbours. If there are no adjacent nodes then we are finished (no more nodes to visit). If there are adjactent nodes we sort them by weight and pass the biggest to FindPath.

When the FindPath function bottoms out (eventually we end up on a node that we can't jump anywhere from) we are left with all the nodes we've visited in the visited list and so then we just need to sort it by weight.

Hope that helps.

Related Topic