Here is the ultimate format I've been thinking about:
cpath along with category names will be appended to all product_info links
All product info links should use only one single form of link, anything else will be redirected (301)

1. form 1:
cat1name-id/cat2name-id/cat3name-id/productname-id

2. form 2:
cat1name-cat2name-cat3name-id1_id2_id3/productname-id