500分求算法：决不失言，欢迎大家来看看
求最优路径的问题：
1. A . .B A和B没有关系;
2. A ._________B A和B有关系(因为线段相连);注意AB是线段不是直线
3. |C
A_____|_____B
|K
D K和相临点A,B,C,D点都有关系,A只和相临点K有关系,
A和B的关系这时已经不存在关系;K点将AB断链;也将CD断链
现在的问题是:
1.在一个图层中有N条已知线段,求每一条线段和其他线段的交点(如K点);
2.标志出每一个点和其相临点(注意1中AB没有关系,2中AB有关系,3中AB没有关系,因为不是相另点)
3.例:A(K),K(A,B,C,D),C(K);
4.如果线段的数目很多,那种方式是最佳算法??最简单的算法是什么?
5.需要注意线段有重复交点的问题(如'米'字型交叉点,交点重复),如何处理?
各位老兄,先谢过了，500分求算法(最好有相应的代码)!
好好学习,互相帮助!
问题点数：100、回复次数：5Top
1 楼zhang_zhibin（blackcat）回复于 2002-12-17 11:38:48 得分 20
我有一段程序是求两个点之间最短路径的，不知道适用不适用于你的问题，QQ：41880902.Top
2 楼cbc（逍遥子）回复于 2002-12-17 11:41:56 得分 10
upTop
3 楼cjy11（）回复于 2002-12-17 13:39:36 得分 0
楼上的兄弟：能否给我发一下，我的邮箱是yueyanglou@sina.com
因为公司规定不能上QQ，不知道晚上你还在QQ上吗？Top
4 楼Aizz（Nova）回复于 2002-12-17 16:23:36 得分 70
楼主的问题我理解的不是很透彻：
1、线段间是不是相连的，即线段的端点之间有没有关系？
2、各线段的交点算不算此图上的点，能不能构成一通路？
假设用如下的结构存储图的每个端点：
struct link //每个端点的数据
{
int distance; //两点间的长度
struct link *next; //相连的下一端点
};
struct link *Node[n]; //n为图的端点数，数组中每个元素都是一个端点
以(3)中的图为例，我们构造一个数组(假设KA=1，KC=3，KB=2，KD=4)：
(Node[0]-Node[4]分别保存A、B、C、D、K相邻最近点的地址)
Node[0](点A):K
Node[1](点B):K
Node[2}(点C):K
Node[3](点D):K
Node[4](点K):A->B->C->D(顺序是根据距离的远近来排的)
找最短路径可以用回溯来找：
假设要找A到D点的最短距离，从Node中取A，得知A最近的点是K；从Node中取K，得知K最近的点是B(除A外)；取B，发现B无法到达D，则回溯到K；K除A,B外最近的是C，取C，又无法到达，回溯；K除A,B,C外最近的是D，找到路径。注意，这个路径并不一定是最短的，要是最短或许还得加上一个权(没想清楚，猜测)，这个权和距离的积可以表示这两点之间的实际“距离”(我也不知道用什么表述，:( )。
献丑，引玉之砖，呵呵。Top
5 楼cjy11（）回复于 2002-12-18 11:21:34 得分 0
楼上的各位兄弟：算法本人已经基本解决，支持谢谢Top
