现在的位置: 首页 > 综合 > 正文

中兴算法题

2013年12月07日 ⁄ 综合 ⁄ 共 895字 ⁄ 字号 评论关闭

一、标题:

求网络中两点之间的路径

二、题目

在一个网络拓扑中(可以支持数千个点的规模),边是双向的,两点之间最多有一条边,所有边的距离相等(也就是权重为1),给出源和目的两个点,需要找出满足条件的路径。

1。找出源和目的之间的一条主用路径。

2。找出源和目的之间的一条备用路径。 备用路径和主用路径至少有一个点或边不相同。

 关于备用路径可能满足下列约束:

 1)和主用路径没有相同的中间节点。

 2)和主用路径没有相同的边。

例如:

示例数据

A_NE_ID,Z_NE_ID

2,28

4,48

9,45

10,1

10,11

11,12

11,2

12,13

13,14

15,23

16,24

拓扑图描述文件

拓扑图文件说明,出于简化的目的,网络拓扑节点用数字表示。


附一个节点较多的测试数据,该数据在在节点631 到节点1980之间找路。

三、初赛阶段要求(含编程语言、开发及运行环境的要求)

1.编程语言:C/C++或者JAVA

2.运行环境:Windows XP

3.源代码和算法说明

4.若采用c/c++,要输出可执行程序;若采用java,给出jar和bat。

5.程序支持命令行参数,

/f后表示拓扑图文件

/s 表示源节点

/d表示目的节点

/c 表示条件(取值1-2,满足上面两个约束条件之一)

/o 表示输出结果文件

如cpath.exe  /ftopolink_example01.txt  /s20  /d32  /c2 /otopolink_result01.txt

表示根据拓扑图文件topolink_example01.txt,计算节点20和节点32之间的主用和备用路径,备用路径要求满足约束条件2。

输出结果文件topolink_result01.txt内容可能的为

main:  20, 21 ,22, 23, 24, 32

backup: 20,29,37, 46,47,48, 40,32

四、初赛阶段审核标准及评价细则

测试结果80分,10组随机网络数据,网络规模:网元结点数目100到5000不等。

在10分钟内完成计算并正确输出结果的,每计算正确一组数据加8分(主备各4分), 路径较短优,耗时较短优。

代码满分5分,可读性及注释。

文档满分15分,要求给出设计思想。

抱歉!评论已关闭.