Say we have N persons and M items (when a person has a certain item, she usually only has one piece). For example,
person 1 has item A, C, D, and wants item F
person 2 has item B, C, and wants E
person 3 has item E, and wants G
You get the idea. So it's basically a supply/demand matching problem, and if we represent this as a person-item matrix, it's gonna be a very sparse one.
So my question would be:
- How do I find the longest possible series (or path) of supply & demand matching among some people and therefore can foster an exchange?
- How do I find the shortest series (or path) that involves more than 2 people (so one-to-one exchange I think I've figured how by using some matrix operations)?
- What would be the complexity for finding longest/shortest paths?
Any advice would be appreciated.