An information processing apparatus includes: a path information acquiring part acquiring path information formed by information indicating connection relationship set between multiple nodes and indicating cost of the connection relationship; an evaluation value giving part giving to the respective nodes included in the path information an evaluation value indicating cost between the node and a reference node; a determining part determining whether to establish as a path the interval between any two of the nodes, on the basis of the connection relationship and a magnitude relation between the evaluation values given to the nodes; and an evaluation value updating part updating the evaluation value of the respective nodes, on the basis of value indicating cost between the respective nodes and a node connected by the established path. Following the determination made by the determining part, the evaluation value updating part executes an evaluation value updating process repeatedly.