What is the most efficient way of finding a path through a small world graph?

Question

I have a sea of weighted nodes with edges linking clusters of nodes together. This graph follows the typical small world layout.

I wish to find a path finding algorithm, which isn't costly on processor power, to find a path along the best possible path where the nodes are the most favorably weighted, the fastest route is not the most important factor. This algorithm, also takes into consideration load bearing, and traffic rerouting.

(sidenote: could neural networks be used here?)

Thanks

---

I'm looking at ACO. Is there anything better than ACO for this kind of problem?

---

Right the A* algorithm finds the least cost or fastest route, without load balancing.

Lets say that the fastest or shortest route is not the most important route, what is more important is following a path where the weighted nodes have a certain value. no1.

no2. If using A* the traffic on that route gets overloaded then suddenly that path is redundant. So as cool as A* is, it doesnt have certain features that ACO ie inherent load balancing.

-- unless im mistaken and misunderstood A*

Then what beats ACO?

---

It really looks like a show down between ACO and A* , there has been so much positive talk about A* , I will certainly look deeper into it.

Firstly in response to David; I can run ACO simulation in the back ground and come up with the best path, so yes there is an initial startup cost but the startup luckily isnt essential. So i can afford to run a simulation multiple times. The one real trouble is finding connected source and destination nodes. Whereas it seems A* will be able to do this quite easily. Now what happens when this network get dreadfully large like in millions of nodes. Will A* be able to scale easily?

I will research A* further. But I leave you with a last question!

Will A* be able to scale as well as Antnet (ACO)?

Answer 1

General notes

Dijkstra's algorithm and it optimised variant A* find the path with "the" minimal cost through your graph. The important things are a) defining your graph correctly and b) defining an appropriate cost function.

In the face of a changing cost function Dijksta requires one to re-calculate the solution.

For load-balancing I would extend Dikstra to not only calculate the optimal path, but use some kind of flood-fill behaviour to create a set of possible paths (sorted by cost) to find alternatives. Only knowledge about the specific problem and cost function can answer whether and how this might work.

Ant Colony Optimisation on the other hand seems to be much more flexible in adapting to a changing cost function, by continuing the iteration after/while the cost function changes.

Efficiency

This depends very much on your problem domain. If you have a good heuristic (see the Complexity section of the A* article) and seldom cost changes then A*'s polynomial runtime might favour repeated re-calculations. ACO on the other hand has to iterate over and over again before converging on an approximate solution. If cost changes occur very frequently, continuing the iteration at a constant rate might be more efficient than updating the A*-solution, since information is retained within the state of the algorithm. ACO doesn't promise the optimal solution, though and probably has higher start-up costs before converging onto a "good" solution. Again that very much depends on your specific domain, graph and cost function as well as your requirements on optimality.

Answer 2

With A*, the path cost does not need to be constant, so you could start with the following graph:

A---1---B---1---C
|               |
\-------1-------/

where we want to go from A to C. Initially, the path finding algorithm will choose the A-C path since A-B-C is 2 whereas A-C is 1. We can add an extra term to the paths:

A---r---B---r---C
|               |
\-------r-------/

with

r(NM) = k(NM) + users(NM) / 10

where

r(NM) is the cost for a connection between N and M,
k(NM) is the constant cost for a connection between N and M,
users(NM) is the number of objects using the connection

As users are added to the system, the route A-C will become more expensive than A-B-C at twenty users (1 + 20/10) = 3, A-B-C is 2. As users are removed from the system, the A-C route will become the best option again.

The real power of the A* is the heuristic you use to calculate the cost of each connection.

Answer 3

The most commonly used algorithm for this problem is A* (A Star), which is a generalized Dijkstra's algorithm search with added heuristics - the purpose of the heuristics is to direct the search towards the search goal so that typical searches finish faster.

This algorithm has many variants, derived versions and improvements, Google search or the Wikipedia page should be a good starting point.

Answer 4

Definitely A*. A* will either find the best path possible or no path at all if no path exists. E.g. the path of this boat has been calculated using A*

_{(source: cokeandcode.com)}

Here's an interactive Java Demo to play with. Please note that this algorithm is slowed down by sleeps, so you see it performing. Without this slow down it would find the path in less than a second.

The algorithm is simple, yet powerful. Each node has 3 values, g is the cost up to this node. h is the estimated cost from this node to the target and f is the sum of both (it's a guess for the full path). A* maintains two lists, the Open and the Closed list. The Open list contains all nodes that have not been explored so far. The Closed list all nodes that have been explored. A node counts as explored if the algorithm has already tested every node connected to this node (connected could only mean horizontally and vertically, but also diagonal if diagonal moves between nodes are allowed).

The algorithm could be described as

1. Let P be the starting point
2. Assign g, h, and f values to P
3. Add P to the open list (at this point P is the only node on that list).
4. Let B be the best node from the Open list (best == lowest f value)
   • If B is the goal node -> quit, you found the path
   • If the Open list is empty -> quit, no path exists
5. Let C be a valid node connected to B
   • Assign g, h, and f to C
   • Check if C is on the Open or Closed List
     • If yes, check whether new path is most efficient (lower f-value)
       • If so, update the path
     • Else add C to the Open List
   • Repeat step 5 for all nodes connected to B
6. Add B to the Closed list (we explored all neighbors)
7. Repeat from step 4.

Also have a look at Wikipedia for implementation details.

Answer 5

I have heard of a NN implementation to handle this kind of problem as well. So if you want to use NNs you will eventually find your way ;-) but they must be inferior in comparison to "genetic algorithms".

If the computational/time consumption is an issue, I would highly suggest using genetic algorithms. This is excactly the type of problems they are exceptional at.

GAs are based on a function that describes your satisfaction for any given solution. You can modify this function to suit your needs (ie. you can include not only path cost but any factor you wish).

Answer 6

Would a common Dijkstra's not be sufficient?

http://improve.dk/generic-dijkstras-algorithm/

Answer 7

Dijkstras algorithm, small example for you

graph = {}

graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["finish"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["finish"] = 5
graph["finish"] = {}

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["finish"] = infinity
print "The weight of each node is: ", costs

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["finish"] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

node = find_lowest_cost_node(costs)
print "Start: the lowest cost node is", node, "with weight",\
    graph["start"]["{}".format(node)]

while node is not None:
    cost = costs[node]
    print "Continue execution ..."
    print "The weight of node {} is".format(node), cost
    neighbors = graph[node]
    if neighbors != {}:
        print "The node {} has neighbors:".format(node), neighbors
    else:
        print "It is finish, we have the answer: {}".format(cost)
    for neighbor in neighbors.keys():
        new_cost = cost + neighbors[neighbor]
        if costs[neighbor] > new_cost:
            costs[neighbor] = new_cost
            parents[neighbor] = node
    processed.append(node)
    print "This nodes we researched:", processed
    node = find_lowest_cost_node(costs)
    if node is not None:
        print "Look at the neighbor:", node

# to draw graph
import networkx
G = networkx.Graph()
G.add_nodes_from(graph)
G.add_edge("start", "a", weight=6)
G.add_edge("b", "a", weight=3)
G.add_edge("start", "b", weight=2)
G.add_edge("a", "finish", weight=1)
G.add_edge("b", "finish", weight=5)

import matplotlib.pyplot as plt
networkx.draw(G, with_labels=True)
plt.show()

print "But the shortest path is:", networkx.shortest_path(G, "start", "finish")