1 Replies - 1329 Views - Last Post: 15 May 2013 - 08:07 PM Rate Topic: -----

#1 blueguitar   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 14-May 13

Path Tracing Algorithm Help

Posted 14 May 2013 - 12:53 AM

I have a graph with a int label and int cost associated with each edge. The graph is represented as an adjacency list. Given an int array, find a path through the graph that traces the values of the ints in the array while at the same time minimizing the cost acrued during the trace. That is, the first edge in the path should have a label that matches the array[0], and the second edge in the path should have a label that matches array[1], etc.... Any node may be the start. Parallel edges are allowed. An edge may be traversed more than once.

Specifically: what is the fastest algorithm to both trace the given path and minimize the cost of the path? How should the labels and costs be represented in the adjacency list?

Right now, I have basically a BFS, where the potential paths are kept in a priority list sorted by the total cost. Only edges that have labels that match the current index of the array (ie, the current path-label) are considered in the BFS. However, this seems rather slow as I'm optimizing for speed?

Is This A Good Question/Topic? 0
  • +

Replies To: Path Tracing Algorithm Help

#2 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon

Reputation: 12316
  • View blog
  • Posts: 45,416
  • Joined: 27-December 08

Re: Path Tracing Algorithm Help

Posted 15 May 2013 - 08:07 PM

Take a look at Dijkstra's algorithm.
Was This Post Helpful? 2
  • +
  • -

Page 1 of 1