Skip to content

Xavier-MaYiMing/The-ripple-spreading-algorithm-for-Shortest-Path-Tour-Problems

BranchesTags

Repository files navigation

The Ripple-Spreading Algorithm for the Shortest Path Tour Problem

The shortest path tour problem aims to find the shortest path that traverses multiple disjoint node subsets in a given order.
Variables Meaning
network Dictionary, {node1: {node2: length, node3: length, ...}, ...}
node_subset List, [[subset1], [subset2], ...]
source List, the source nodes of this subproblem of SPTP
destination List, the destination nodes of this subproblem of SPTP
init_time List, the initial time that should generate initial ripples at source nodes
init_radius List, the initial radius of initial ripples at source nodes
nn The number of nodes
neighbor Dictionary, {node1: [the neighbor nodes of node1], ...}
v The ripple-spreading speed (i.e., the minimum length of arcs)
t The simulated time index
nr The number of ripples - 1
epicenter_set List, the epicenter node of the ith ripple is epicenter_set[i]
path_set List, the path of the ith ripple from the source node to node i is path_set[i]
radius_set List, the radius of the ith ripple is radius_set[i]
active_set List, active_set contains all active ripples
Omega Dictionary, Omega[n] = i denotes that ripple i is generated at node n

Example (RSA4SPTP.py)

if __name__ == '__main__':
    test_network = {
        0: {1: 2, 2: 3, 3: 3},
        1: {0: 2, 3: 2},
        2: {0: 3, 3: 3},
        3: {0: 3, 1: 2, 2: 3, 4: 2, 5: 3, 6: 3},
        4: {3: 2, 6: 2},
        5: {3: 3, 6: 3},
        6: {3: 3, 4: 2, 5: 3},
    }
    subset = [[0], [1, 3], [4, 5], [6]]
    print(main(test_network, subset))
Output
{'path': [0, 3, 4, 6], 'length': 7}

The Ripple-Spreading Algorithm for the Many-to-Many Shortest Path Tour Problem

The shortest path tour problem aims to find the shortest path that traverses multiple disjoint node subsets in a given order. The many-to-many shortest path tour problem has multiple sources and destinations. It aims to determine the shortest path tour for every source node to any one of the destination nodes.
Variables Meaning
network Dictionary, {node1: {node2: length, node3: length, ...}, ...}
node_subset List, [[subset1], [subset2], ...]
source List, the source nodes of this subproblem of SPTP
destination List, the destination nodes of this subproblem of SPTP
init_time List, the initial time that should generate initial ripples at source nodes
init_radius List, the initial radius of initial ripples at source nodes
nn The number of nodes
neighbor Dictionary, {node1: [the neighbor nodes of node1], ...}
v The ripple-spreading speed (i.e., the minimum length of arcs)
t The simulated time index
nr The number of ripples - 1
epicenter_set List, the epicenter node of the ith ripple is epicenter_set[i]
path_set List, the path of the ith ripple from the source node to node i is path_set[i]
radius_set List, the radius of the ith ripple is radius_set[i]
active_set List, active_set contains all active ripples
Omega Dictionary, Omega[n] = i denotes that ripple i is generated at node n

Example (RSA4m2mSPTP.py)

if __name__ == '__main__':
    test_network = {
        0: {1: 2, 2: 3, 3: 3},
        1: {0: 2, 3: 2},
        2: {0: 3, 3: 3},
        3: {0: 3, 1: 2, 2: 3, 4: 2, 5: 3, 6: 3},
        4: {3: 2, 6: 2},
        5: {3: 3, 6: 3},
        6: {3: 3, 4: 2, 5: 3},
    }
    subset = [[0, 2], [1, 3], [5, 6]]
    print(main(test_network, subset))
Output
{
    0: {'path': [0, 3, 5], 'length': 6}, 
    2: {'path': [2, 3, 5], 'length': 6},
}

The Ripple-Spreading Algorithm for the k Shortest Path Tour Problem

The shortest path tour problem (SPTP) aims to find the shortest path that traverses multiple disjoint node subsets in a given order. The k-SPTP aims to find the k shortest paths for the SPTP.
Variables Meaning
network Dictionary, {node1: {node2: length, node3: length, ...}, ...}
node_subset List, [[subset1], [subset2], ...]
source List, the source nodes of this subproblem of SPTP
destination List, the destination nodes of this subproblem of SPTP
init_time List, the initial time that should generate initial ripples at source nodes
init_radius List, the initial radius of initial ripples at source nodes
init_path List, the initial path for each initial ripple
k The k shortest paths
nn The number of nodes
neighbor Dictionary, {node1: [the neighbor nodes of node1], ...}
v The ripple-spreading speed (i.e., the minimum length of arcs)
t The simulated time index
nr The number of ripples - 1
epicenter_set List, the epicenter node of the ith ripple is epicenter_set[i]
path_set List, the path of the ith ripple from the source node to node i is path_set[i]
radius_set List, the radius of the ith ripple is radius_set[i]
active_set List, active_set contains all active ripples
Omega Dictionary, Omega[n] = i denotes that ripple i is generated at node n

Example 1 (RSA4kSPTP.py)

if __name__ == '__main__':
    # Example 1
    test_network = {
        0: {1: 3, 2: 3},
        1: {0: 3, 2: 3, 3: 5},
        2: {0: 3, 1: 3, 3: 4},
        3: {1: 5, 2: 4},
    }
    subset = [[0], [1], [3]]
    print(main(test_network, subset, 2))
Output
[
    {'path': [0, 1, 3], 'length': 8}, 
    {'path': [0, 1, 2, 3], 'length': 10}
]

Example 2 (RSA4kSPTP.py)

This example aims to find the 8 shortest paths for the k-SPTP on a randomly generated network with 49 nodes.
if __name__ == '__main__':
    # Example 2
    def generate_network():
        x = []  # x坐标
        y = []  # y坐标
        T = [[0], [11, 12, 18, 19], [29, 30, 36, 37], [48]]
        connect_list = [0, 1, 2, 3, 4, 5, 6, 7, 13, 14, 20, 21, 27, 28, 34, 35, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50]
        for i in range(7):
            for j in range(7):
                x.append(i * 10)
                y.append(j * 10)
        for i in range(1, 49):
            x[i] = x[i] + random.uniform(-2, 2)
            y[i] = y[i] + random.uniform(-2, 2)
        x1 = []
        y1 = []
        x2 = []
        y2 = []
        x3 = []
        y3 = []
        for i in range(49):
            if i not in T[1] and i not in T[2]:
                x1.append(x[i])
                y1.append(y[i])
        for i in range(len(T[1])):
            x2.append(x[T[1][i]])
            y2.append(y[T[1][i]])
        for i in range(len(T[2])):
            x3.append(x[T[2][i]])
            y3.append(y[T[2][i]])
        adjacent_matrix = []
        for i in range(49):
            adjacent_matrix.append([])
            for j in range(49):
                if i in connect_list and j in connect_list and math.sqrt((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2) < 15:
                    adjacent_matrix[i].append(1)
                else:
                    adjacent_matrix[i].append(0)
        p1 = 0.7
        p2 = 0.05
        p3 = 0.03
        for i in range(49):
            for j in range(49):
                if (abs(i - j) == 1 or abs(i - j) == 7) and math.sqrt(
                        (x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2) < 20:  # 横或竖相连
                    if random.random() < p1:
                        adjacent_matrix[i][j] = 1
                        adjacent_matrix[j][i] = 1
                if (abs(i - j) == 8 or abs(i - j) == 6) and math.sqrt(
                        (x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2) < 30:  # 对角线相连
                    if random.random() < p2:
                        adjacent_matrix[i][j] = 1
                        adjacent_matrix[j][i] = 1
                if (abs(i - j) == 2 or abs(i - j) == 14) and math.sqrt((x[i] - x[j]) ** 2 + (
                        y[i] - y[j]) ** 2) < 30 and i in connect_list and j in connect_list:  # 两横线或两竖线相连
                    if random.random() < p3:
                        adjacent_matrix[i][j] = 1
                        adjacent_matrix[j][i] = 1
        for i in range(1, len(T) - 1):
            for j in T[i]:
                adjacent_matrix[j][j + 7] = 1
                adjacent_matrix[j + 7][j] = 1
                adjacent_matrix[j][j - 7] = 1
                adjacent_matrix[j - 7][j] = 1
                adjacent_matrix[j][j + 1] = 1
                adjacent_matrix[j + 1][j] = 1
                adjacent_matrix[j][j - 1] = 1
                adjacent_matrix[j - 1][j] = 1
        network = {}
        for i in range(49):
            network[i] = {}
            for j in range(49):
                if i != j and adjacent_matrix[i][j] != 0:
                    temp_dist = math.sqrt((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2)
                    network[i][j] = temp_dist
        return x, y, network


    def draw_path(x, y, network, subset, path, length, ind):
        x1 = []
        y1 = []
        x2 = []
        y2 = []
        x3 = []
        y3 = []
        for i in range(len(x)):
            if i in subset[1]:
                x2.append(x[i])
                y2.append(y[i])
            elif i in subset[2]:
                x3.append(x[i])
                y3.append(y[i])
            else:
                x1.append(x[i])
                y1.append(y[i])
        plt.figure(dpi=600)
        for i in range(48):
            for j in range(i, 49):
                if j in network[i].keys():
                    temp_x = [x[i], x[j]]
                    temp_y = [y[i], y[j]]
                    i_index = 49
                    j_index = 0
                    if i in path and j in path:
                        i_index = path.index(i)
                        j_index = path.index(j)
                    if abs(i_index - j_index) == 1 or (j_index - 1 >= 0 and path[j_index - 1] == i) or (
                            i_index + 1 < len(path) and path[i_index + 1] == j):
                        plt.plot(temp_x, temp_y, 'black', linewidth=2)
                    else:
                        plt.plot(temp_x, temp_y, 'springgreen', linewidth=2)
        plt.scatter(x1, y1, c='springgreen', s=150)
        plt.scatter(x2, y2, c='darkred', alpha=1, s=150)
        plt.scatter(x3, y3, c='darkblue', alpha=1, s=150)
        plt.title(str(ind) + ', length = ' + str(round(length, 5)))
        plt.xticks(())
        plt.yticks(())
        plt.savefig('D://' + str(ind) + '.png')
        plt.show()

    x, y, test_network = generate_network()
    subset = [[0], [11, 12, 18, 19], [29, 30, 36, 37], [48]]
    result = main(test_network, subset, 8)
    print(result)
    for i in range(len(result)):
        draw_path(x, y, test_network, subset, result[i]['path'], result[i]['length'], i + 1)
Output

[
    {'path': [0, 1, 2, 10, 17, 18, 17, 24, 23, 30, 31, 32, 33, 34, 41, 48], 'length': 150.1495608090849}, 
    {'path': [0, 1, 2, 10, 17, 18, 17, 24, 23, 30, 37, 44, 45, 46, 47, 48], 'length': 150.63572706262775}, 
    {'path': [0, 1, 2, 10, 17, 18, 25, 32, 31, 30, 31, 32, 33, 34, 41, 48], 'length': 151.2016145482568}, 
    {'path': [0, 1, 8, 9, 17, 18, 17, 24, 23, 30, 31, 32, 33, 34, 41, 48], 'length': 151.27653543201578}, 
    {'path': [0, 1, 2, 10, 17, 18, 17, 24, 23, 30, 31, 32, 39, 40, 47, 48], 'length': 151.29119265478346}, 
    {'path': [0, 1, 2, 10, 11, 10, 17, 24, 23, 30, 31, 32, 33, 34, 41, 48], 'length': 151.44287618906438}, 
    {'path': [0, 1, 2, 10, 17, 18, 25, 32, 31, 30, 37, 44, 45, 46, 47, 48], 'length': 151.68778080179965}, 
    {'path': [0, 1, 8, 9, 17, 18, 17, 24, 23, 30, 37, 44, 45, 46, 47, 48], 'length': 151.76270168555862}
]

About

The ripple-spreading algorithm for shortest path tour problems

Topics

ripple-spreading-algorithm shortest-path-tour-problem many-to-many-shortest-path-tour-problem k-shortest-path-tour-problem

Resources

Readme
Activity

Stars

1 star

Watchers

1 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages