Path calculating method, program and calculating apparatus

Abstract

Calculation of a shortest path connecting two nodes of a network involves steps of: comparing a distance of a first communication path between, from among the plurality of nodes, a starting node as a starting point of a communication path and an adjacent node located adjacent to the starting node, to a distance of a second communication path which has already been calculated other than the first communication path and has already been stored; either taking the first communication path as a candidate of the shortest path if the distance of the first communication path is shorter than the second communication path, or taking the second communication path as a candidate of the shortest path if the distance of the first communication path is not shorter than the second communication path; and taking the adjacent node as a next starting node in the comparison step.

1 . A path calculating method in a network in which a plurality of nodes are connected by links, a computer calculates the shortest path which is the shortest communication path between two nodes of the plurality of nodes,
 wherein the computer comprises:
 a control unit; and a storage unit that stores therein information including the shortest path between the nodes, 
   wherein the control unit performs
 a comparison step of comparing a distance of a first communication path between, from among the plurality of nodes, a starting node as a starting point of a communication path and an adjacent node located adjacent to the starting node, to a distance of a second communication path which has already been calculated other than the first communication path and has already been stored in the storage unit, 
 a step of, if the distance of the first communication path is shorter than the second communication path, taking the first communication path as a candidate of the shortest path, and 
 a step of, if the distance of the first communication path is not shorter than the second communication path, taking the second communication path as a candidate of the shortest path, and 
   wherein the control unit further performs
 the comparison step taking the adjacent node as a next starting node. 
   
     
     
         2 . The path calculating method according to  claim 1 ,
 wherein the control unit performs:
 a step of comparing a distance of a path via a shortest path tree made up of the candidate shortest paths to an end node of the two nodes to a distance of a path via a path tree other than the shortest path tree to the end node of the two nodes; and 
 a step of, according to a result of the comparison, taking whichever is shorter between the distance of the path via the shortest path tree made up of the candidate shortest paths to the end node of the two nodes or the distance of the path via the path tree other than the shortest path tree to the end node of the two nodes, as the shortest path to the end node of the two nodes. 
   
     
     
         3 . The path calculating method according to  claim 1 ,
 wherein the control unit performs a step of, if the distance of the first communication path is smaller than a recorded value recorded in the end node, updating the recorded value to the distance of the first communication path.   
     
     
         4 . The path calculating method according to  claim 2 ,
 wherein the control unit performs
 a step of, if the distance via the shortest path tree to the end node of the two nodes is shorter than the distance of the path via the path tree other than the shortest path tree to the end node of the two nodes, updating a recorded value recorded in the end node, to a distance of the path via the shortest path tree. 
   
     
     
         5 . A program which, in a network in which a plurality of nodes are connected by links, calculates the shortest path which is the shortest communication path between two nodes of the plurality of nodes,
 wherein the program causes a computer to perform
 a comparison procedure of comparing a distance of a first communication path between, from among the plurality of nodes, a starting node as a starting point of a communication path and an adjacent node located adjacent to the starting node, to a distance of a second communication path which has already been calculated other than the first communication path and has already been stored in the storage unit, 
 a procedure of, if the distance of the first communication path is shorter than the second communication path, taking the first communication path as a candidate of the shortest path, and 
 a procedure of, if the distance of the first communication path is not shorter than the second communication path, taking the second communication path as a candidate of the shortest path, and 
   wherein the program performs
 the comparison procedure taking the adjacent node as a next starting node. 
   
     
     
         6 . The program according to  claim 5 ,
 wherein the program causes a computer to perform
 a step of comparing a distance of a path via a shortest path tree made up of the candidate shortest paths to an end node of the two nodes to a distance of a path via a path tree other than the shortest path tree to the end node of the two nodes; and 
 a step of, according to a result of the comparison, taking whichever is shorter between the distance of the path via the shortest path tree made up of the candidate shortest paths to the end node of the two nodes or the distance of the path via the path tree other than the shortest path tree to the end node of the two nodes, as the shortest path to the end node of the two nodes. 
   
     
     
         7 . A calculating apparatus in a network in which a plurality of nodes are connected by links, the calculating apparatus calculating the shortest path which is the shortest communication path between two nodes of the plurality of nodes, comprising:
 a storage unit that stores therein information including the shortest path between the nodes; and   a control unit that: compares a distance of a first communication path between, from among the plurality of nodes, a starting node as a starting point of a communication path and an adjacent node located adjacent to the starting node, to a distance of a second communication path which has already been calculated other than the first communication path and has already been stored in the storage unit; if the distance of the first communication path is shorter than the second communication path, takes the first communication path as a candidate of the shortest path; if the distance of the first communication path is not shorter than the second communication path, takes the second communication path as a candidate of the shortest path; and takes the adjacent node as a next starting node and compares a distance of the first communication path to a distance of the second communication path.   
     
     
         8 . The calculating apparatus according to  claim 7 ,
 wherein the control unit: compares a distance of a path via a shortest path tree made up of the candidate shortest paths to an end node of the two nodes to a distance of a path via a path tree other than the shortest path tree to the end node of the two nodes; and, according to a result of the comparison, takes whichever is shorter between the distance of the path via the shortest path tree made up of the candidate shortest paths to the end node of the two nodes or the distance of the path via the path tree other than the shortest path tree to the end node of the two nodes, as the shortest path to the end node of the two nodes.   
     
     
         9 . The calculating apparatus according to  claim 7 ,
 wherein, if the distance of the first communication path is smaller than a recorded value recorded in the end node, the control unit updates the recorded value to the distance of the first communication path.   
     
     
         10 . The calculating apparatus according to  claim 7 ,
 wherein, if the distance via the shortest path tree to the end node of the two nodes is shorter than the distance of the path via the path tree other than the shortest path tree to the end node of the two nodes, the control unit updates a recorded value recorded in the end node, to a distance of the path via the shortest path tree.