兰州交通大学学报
蘭州交通大學學報
란주교통대학학보
Journal of Lanzhou Jiaotong University
2015年
4期
157-159,165
,共4页
最小点覆盖问题%Dijkstra 算法%近似算法%时间复杂性
最小點覆蓋問題%Dijkstra 算法%近似算法%時間複雜性
최소점복개문제%Dijkstra 산법%근사산법%시간복잡성
minimum vertex covering problem%Dijkstra algorithm%approximation algorithm%time complex
基于经典的最短路算法———Dijkstra 算法，以最短路路长的最大值为标准，按照一定原则选择点覆盖的顶点，得出了最小点覆盖问题的一个近似算法，其时间复杂性为 O（n3）．最后给出了一个近似比为1．067的算例，阐释了算法的实现过程及有效性．
基于經典的最短路算法———Dijkstra 算法，以最短路路長的最大值為標準，按照一定原則選擇點覆蓋的頂點，得齣瞭最小點覆蓋問題的一箇近似算法，其時間複雜性為 O（n3）．最後給齣瞭一箇近似比為1．067的算例，闡釋瞭算法的實現過程及有效性．
기우경전적최단로산법———Dijkstra 산법，이최단로로장적최대치위표준，안조일정원칙선택점복개적정점，득출료최소점복개문제적일개근사산법，기시간복잡성위 O（n3）．최후급출료일개근사비위1．067적산례，천석료산법적실현과정급유효성．
Based on Dijkstra algorithm,an approximation algorithm is obtained for minimum vertex covering problem.In the process of getting the algorithm,the maximum value of the shortest path length is considered as a standard,and some criteria are defined.The time complex of the al-gorithm is O(n3 ).In the end,an example is given to illustrate the process of the algorithm,and its approximate ratio is 1.067.
