How are paths found in Lightning Network? I understand now how multihop payments can work in LN, but how do we discover payment paths in Lightning Network in the first place?  Obviously you'd need to take into account the available capacity of the route, and you'd want to discover the cheapest path.

There shouldn't be a payment channel directory, so would it rely on a peer-based search?
Note: This answer was written in Spring 2016 and has since been overtaken by an actual spec and multiple implementations. I'm hoping to update this answer shortly.



Summarizing mostly from r/bitcoin: How are paths found in Lightning Network?, the currently suggested routing would be similar to the Border Gateway Protocol.

At intervals, the following process is initiated:


A beacon node B is selected via a pseudo-random process.
Neighbors of B broadcast their shortest route to B to their neighbors.
The neighbors of neighbors of B now become aware of a route to B and in turn broadcast their shortest route to B.
This cascades through the network until every reachable node has broadcasted their shortest route to the beacon node B.
Whenever a node becomes aware of a new shorter route, it broadcasts this updated shortest route as well.
After a short wait, start from top with a new beacon node B1.


Nodes remember their shortest routes to a number of previously selected beacon node.

Now, Alice wants to send 0.3BTC to Bob.
Alice has shortest routes to B, B1, and B2. Bob just came online and only knows B2. They add together their respective paths to B2 and thus find a path: 

     Alice → N1 → N2 → B2 ← N3 ← Bob


If they have multiple common beacons, they can also compare different paths, and check whether any earlier nodes in their routes match. If they instead had found:

     Alice → N1 → N2 → B2 ← N2 ← Bob


They could shorten the route to:

     Alice → N1 → N2 ← Bob


Altogether, "shortest" would be some combination of reachable, sufficient liquidity, lowest fee, fewest hops, and most reliable. As Hash Time Lock Contracts are nearly trustless (only potentially locking your money for some time), and operating a routing wallet should have low resource requirements, it seems likely that the payment routing market should achieve a healthy competition, therefore discouraging nodes to lock money by establishing channels just to earn fees from routing. Payment channels between nodes that have some form of regular business relationship seem more likely as there is an immediate benefit.



Sources: harda, mmeijeri, mmeijeri.