The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

About graphs

i have problem in finding all paths between two given nodes of the graph.all paths sholud not have some node more than once.can anybody help me.
somashekar.v.a Send private email
Sunday, December 11, 2005
We try not to do homework for people here.
Ryan Phelps Send private email
Monday, December 12, 2005
Gosh Ryan don't be mean to the poor fellow.

Here's how it's done. First calculate which path is shortest. This will be a simple exercise. Then, find the second shortest path. Keep going under you have found the longest path. Now, count how many paths you have. It will be helpful to use a red-black tree for this.

Good luck!
Art Wilkins
Monday, December 12, 2005
Finding the longest path between two nodes on a graph is np-hard. It is a superset of the hamilton path problem.

Monday, December 19, 2005

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz