求网络中两点之间的路径

阅读量：3941 次

发布时间：2019-05-24

本文共 5435 字，大约阅读时间需要 18 分钟。

文章目录

一、标题：

求网络中两点之间的路径

二、题目

在一个网络拓扑中（可以支持数千个点的规模），边是双向的，两点之间最多有一条边，所有边的距离相等（也就是权重为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

17,25

18,19

18,1

20,21

20,29

20,3

21,22

22,23

23,24

24,32

26,27

26,34

27,28

27,35

28,36

29,37

30,31

32,40

32,33

32,31

33,25

33,41

36,44

37,38

37,45

39,30

39,4

40,5

40,49

43,42

43,50

43,6

44,43

45,7

45,8

46,37

46,47

47,48

48,40

拓扑图描述文件

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

结果：

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

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

三、代码实现

此算法主要是对狄杰斯特拉算法的应用，还有可以改进的地方。

如果能够计算出当前所处的位置与目的节点之间的最短距离，可以改为实现。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define INF 0x3f3f3f3f//深度优先遍历存放未找到最短路径的节点struct Index{ Index(int id = 0,int d = INF):ID(id),dis(d){ } int ID; int dis;};struct Node{ Node(int id = 0,int d = INF):ID(id),dis(d){ } int ID; //当前节点，作为索引 int dis; //源节点到当前节点的最短距离, 更新后重新写入所有的dis int prev; //当前节点的前驱节点 vector
         
           neighbor; //存放当前节点的邻居节点，其邻居节点中也存储了该节点};class comp{ public: bool operator()(const Index &left, const Index &right) { if(left.dis < right.dis) { return true; } else if(left.dis == right.dis && left.ID < right.ID) { return true; } return false; }};//DFS 广度优先遍历//查找到一条可行路径就将这条可行路径上的每一个节点删除//所有存储该节点的信息的其他节点的更新节点的存储信息class Myclass{ public: //初始化源节点和目的节点 Myclass(int s = 0,int d = 0):_src(s),_des(d){ } //初始化网络节点 void InitNet(string str) { FILE *fp = fopen(str.c_str(),"r"); char buff[128] = { 0}; int src,des; while(fgets(buff,127,fp) > 0) { sscanf(buff,"%d,%d",&src,&des); auto it = _net.find(src); if(it == _net.end()) { _net[src] = Node(src); } it = _net.find(des); if(it == _net.end()) { _net[des] = Node(des); } _net[src].neighbor.push_back(des); _net[des].neighbor.push_back(src); } fclose(fp); //与源点直连的节点初始化dis为1 auto it = _net.find(_src); it->second.dis = 0; if(it != _net.end()) { auto it_neighbor = it->second.neighbor.begin(); for(; it_neighbor != it->second.neighbor.end(); ++it_neighbor) { //与源节点相邻的节点的前驱节点改为源节点的编号 _net[*it_neighbor].dis = 1; _net[*it_neighbor].prev = _src; } } } //更新所有与关联节点相关的节点的邻居表的信息和最短距离的信息 void update(unordered_map
          
            &net,vector
           
             &path) { //判断节点中,如果节点为空，则说明目的节点与源节点直连，单独处理 //因为存放邻居节点的数据结构为 vector 所以节点的删除时间复杂度为O(n) n为邻居节点的个数 if(path.empty()) { //删除两个节点之间的边 auto it_src = net.find(_src); auto it = it_src->second.neighbor.begin(); for(; it != it_src->second.neighbor.end(); ++it) { if(*it == _des) { it_src->second.neighbor.erase(it); break; } } auto it_des = net.find(_des); for(it = it_des->second.neighbor.begin(); it != it_des->second.neighbor.end(); ++it) { if(*it == _src) { it_des->second.neighbor.erase(it); break; } } //两个节点之间的距离设置为不可达 //因为两个节点一个为源节点，一个为目的节点，所以并不删除节点 it_des->second.dis = INF; return ; } //在网络中删除路径中的所有中间节点 auto it_path = path.begin(); for(; it_path != path.end(); ++it_path) { auto it_node = net.find(*it_path); //存在需要删除的节点 if(it_node != net.end()) { for(auto it = it_node->second.neighbor.begin() ;it != it_node->second.neighbor.end() ;++it) { //其他节点中删除对当前节点的记录 int size = net[*it].neighbor.size(); for(int i = 0; i < size; i++) { if(net[*it].neighbor[i] == *it_path) { net[*it].neighbor.erase(net[*it].neighbor.begin()+i); break; } } } //删除节点 net.erase(it_node); } //否则的话说明当前节点已经被删除，？是否会存在这种情况 } //删除完成后,更新dis auto it = net.begin(); for(;it != net.end(); ++it) { it->second.dis = INF; } it = net.find(_src); it->second.dis = 0; //更新与源节点直连的节点的最短距离 for(auto it_nei = it->second.neighbor.begin() ; it_nei != it->second.neighbor.end() ; ++it_nei) { net[*it_nei].dis = 1; } } //DFS 遍历 //程序主要的运行时间为广度优先的查找，每找到一条最短路径都要删除路径中经过的中间节点 //程序运行有明显的先后的执行顺序，所以不适合并行程序的设计 bool DFS(vector
            
              &path,unordered_map
             
               &net) { queue
              
                S; //定义S表，存放找到最短路径的节点 set
               
                 V; //定义V表，存放未找到最短路径的节点 ,按最短路径优先，允许重复 //添加索引 auto it = net.begin(); for(; it != net.end(); ++it) { V.insert(Index(it->first,it->second.dis)); } // 第一个节点是源节点，dis = 0 , 最小 删除源节点 V.erase(V.begin()); //在已经查到最短路径的表中添加源节点 S.push(_src); //狄杰斯特拉算法找最短路径 while(!V.empty()) { auto it_V = V.begin(); if(it_V->ID == _des) { break; } if(it_V->dis >= INF) { return false; } S.push(it_V->ID); auto it_neighbor = net[it_V->ID].neighbor.begin(); for(; it_neighbor != net[it_V->ID].neighbor.end(); ++it_neighbor) { auto it_tmp = net.find(*it_neighbor); if(it_tmp != net.end() && it_tmp->second.dis > it_V->dis + 1) { V.erase(Index(*it_neighbor,it_tmp->second.dis)); it_tmp->second.dis = it_V->dis + 1; it_tmp->second.prev = it_V->ID; V.insert( Index(*it_neighbor,it_tmp->second.dis) ); } } //删除最顶端的节点 V.erase(it_V); } //循环中出来，要么存在最短路径，要么不存在 if(!V.empty()) { int k = _des; while(net[k].prev != _src) { path.push_back(net[k].prev); k = net[k].prev; } } return true; } //总控制函数 //如果目的节点与源节点直连，可能会陷入死循环，可以删除源节点与目的节点之间的边使得此路不通 vector
                
                 
                   > contral(unordered_map
                  
                    &net) { vector
                   
                    
                      > Path; //存放路径 while( 1 ) { //找一条最短路径 vector
                     
                       res; //找不到最短路径，直接退出 if(!DFS(res,net)) { break; } //更新网络 循环查找， Path.push_back(res); update(net,res); } return Path; } unordered_map
                      
                        getNet() { return _net; }private: unordered_map
                       
                         _net; int _src; //源节点 int _des; //目的节点 };//修改为A*算法//修改为A*算法的难度主要在如何计算从当前节点到目的节点的最短距离//数据的分布规律int main(){ Myclass my(631,1980); //Myclass my(20,32); string str = "234.txt"; my.InitNet(str); unordered_map
                        
                          net = my.getNet(); vector
                         
                          
                            > path = my.contral(net); for(int i = 0; i < path.size();i++) { for(auto val:path[i]) { cout << val << " "; } cout << endl; } return 0;}