两种最短路径

本文收录了Dijkstra和floyd求解最短路径的算法实现。这两个算法建议看看算法导论这本书，网上乱七八糟的什么错误都敢往上写。

• Dijkstra类似贪心算法，从某个点出发不断的贪心，求得和其他点的最短路径。

• Floyd为动态规划算法，不断的更新子问题，使得每两点之间的距离不断的减小。

如果问题发生了变化，比如最短路径不唯一时，我想走顶点最少的路径；或者在两点之间，我想走那个顶点最少的路径，又该怎么转化呢？则称为最短路最小顶点问题，本文也给出自己的解决方案写的太烂，删除了。

如果对本文有疑问或者想找男朋友，可以联系我，点击此处有我联系方式。

Floyd算法

import random
import time
import numpy as np 
import sys

def random_matrix(vex_num):
    '''
    随机图顶点矩阵生成器
    输入：顶点个数，即矩阵维数
    '''
    data_matrix =[
                [0, 50, sys.maxsize, 40, 25, 10], 
                [50, 0, 15, 20, sys.maxsize, 25], 
                [sys.maxsize, 15, 0, 10, 20, sys.maxsize], 
                [40, 20, 10, 0, 10, 25],
                [25, sys.maxsize, 20, 10, 0, 55], 
                [10, 25, sys.maxsize, 25, 55, 0]
            ]

    return data_matrix
 
 
def floyd(data_matrix, vex_num):

    dist_matrix = data_matrix
    path_matrix = [[1, 2, 3, 4, 5, 6]] * 6

    for k in range(vex_num):
        for i in range(vex_num):
            for j in range(vex_num):
                temp = dist_matrix[i][k] + dist_matrix[k][j]
                if dist_matrix[i][j] > temp:
                    dist_matrix[i][j] = temp
                    path_matrix[k][i] = path_matrix[i][j]
    return dist_matrix, path_matrix
      

if __name__  ==  '__main__':

    vex_num = 6
    data_matrix = random_matrix(vex_num)
    dist_matrix , path_matrix = np.array(floyd(data_matrix, vex_num))
    
    for i in range(vex_num):
        for j in range(vex_num):
            print ( str(i) + '----->' + str(j) + '  shortest_path distance is : ', dist_matrix[i][j])

    print(path_matrix)

Dijkstra 算法

# This is a program to illustrate the detail of dijkstra algorithm.
# 这里为了引入无穷大这个概念
import sys

adjacency_matrix = [
                [0, 50, sys.maxsize, 40, 25, 10], 
                [50, 0, 15, 20, sys.maxsize, 25], 
                [sys.maxsize, 15, 0, 10, 20, sys.maxsize], 
                [40, 20, 10, 0, 10, 25],
                [25, sys.maxsize, 20, 10, 0, 55], 
                [10, 25, sys.maxsize, 25, 55, 0]
            ]
            
node_number = len(adjacency_matrix[0])
#已经访问过的节点列表，0与1表示了有与无的概念，1表示访问过
visited = [0 for i in range(node_number)]    
visited[0] = 1

#表示与起始点的距离
want_node = 0
path = adjacency_matrix[want_node]    

for i in range(1, node_number):

    min_value_index = int()
    mindis = sys.maxsize

    for j in range(1, node_number):
        if visited[j] == 1:
            continue
        if path[j] < mindis:
            min_value_index = j
            mindis = path[j]

    # 每次更新最短
    visited[min_value_index] = 1

    for j in range(1, node_number):
        if visited[j] == 0:
            #如果新加入的点使得距离更短则刷新
            if path[j] > path[min_value_index] + adjacency_matrix[min_value_index][j]:  
                path[j] = path[min_value_index] + adjacency_matrix[min_value_index][j]


for i in range(0, len(path)):
    print(str(want_node) + ' -> ' + str(i) + ' distance is : ' + str(path[i]))