I'd simply like to expand on Andrew's answer and mention that the routing algorithm used to find the various hops towards your final destination payment will also impact your resulting fee.
The idea is that channels sometimes become almost exhausted - where most of the money is pushed towards one direction. This is bad for people because it would mean that their channels cannot be reused; you'd have to open a new channel for new payments, hence on-chain transactions.
If a channel is almost exhausted, the person of the channel with less money (exhausted towards her) will want payments routed towards her to allow her channel to be full again so she can make more payments on that same channel without reopening a new one.
She will actually want to pay if someone chooses her channel to route their payments -- hence sometimes you'll have negative fees.
This means that a routing algorithm will actually look for paths where you actually get paid (negative fees) because you'd be rebalancing some channels along the way.