福
福

雨辰枫司的小栈

最短路径

  • ~3.73K 字
  • 条评论
  1. 1. 图的存储
  2. 2. BFS(广度优先搜索)算法 (无权图、单源最短路)
  3. 3. Dijkstra算法 (带权图、无权图、无负权、单源最短路)
  4. 4. dellman-ford算法(带权图、无权图、单源最短路)
  5. 5. Floyd算法 (带权图、无权图、无负环、各个顶点之间的最短路径)

求一个图的最短路径。

图的存储

示例用邻接矩阵来存储图 n表示大小,maxNum表示无穷,array表示图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys

class Graph():
    def __init__(self,n:int,maxNum = sys.maxsize,array = []) -> None:
        if array != []:
            self.arr = array
        else:
            self.arr = [[maxNum] * n for i in range(n)]
        self.maxNum = maxNum
        self.size = n
    
    def add(self,a:int,b:int,weights) -> None:
        self.arr[a][b] = weights

    def delete(self,a,b) -> int:
        weights = self.arr[a][b]
        self.arr[a][b] = self.maxNum
        return weights

BFS(广度优先搜索)算法 (无权图、单源最短路)

广度优先搜索主要用于求解无权图或者等权图的最短路径，主要由一个点向外扩散，第一次到达的路径就是源点到达该点的最短路径。

其过程就是用一个表(table)来存储每个节点的访问情况，初始化时将一个顶点加入队列(queue)。

将队头取出,将它在表(table)内的状态设置为True(表示已经访问过),将它未访问的邻点加入队列(queue),循环该过程，直到每个顶点都被访问过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def bfs(self,startPoint = 0):
    table = [False] * self.size
    queue = [0] * self.size
    start,end = 0,-1
    graph = [self.maxNum] * self.size 
    layer = 0

    #初始化
    end += 1
    table[startPoint] = True
    queue[end] = startPoint

    while start <= end:
        for i in range(end - start + 1):
            cur = queue[start]
            start += 1
            graph[cur] = layer
            for i in range(self.size):
                if self.arr[cur][i] != self.maxNum and not table[i]:
                    end += 1
                    queue[end] = i
                    table[i] = True
        layer += 1
    
    return graph

返回的是startPoint到各个顶点的最短距离

Dijkstra算法 (带权图、无权图、无负权、单源最短路)

与prim算法差不多，prim是到集合的距离，而Dijkstra是到某个点的距离
这里不做过多叙述，可以参考最小生成树的prim算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def dijkstra(self,startPrint = 0):
    point = [False] * self.size
    distance = [self.maxNum] * self.size
    precursor = [-1] * self.size

    # 初始化
    distance[startPrint] = 0

    for i in range(self.size):
        min = self.maxNum
        count = -1
        for j in range(self.size):
            if min > distance[j] and not point[j]:
                min = distance[j]
                count = j

        if count != -1:
            point[count] = True
            for j in range(self.size):
                if self.arr[count][j] != self.maxNum:
                    if (distance[count] + self.arr[count][j] < distance[j] and not point[j]) or (precursor[j] == -1 and j != startPrint):
                        distance[j] = distance[count] + self.arr[count][j]
                        precursor[j] = count
        
    return distance,precursor

dellman-ford算法(带权图、无权图、单源最短路)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def dellmanFord(self,startPoint = 0):
    graph = []
    for i in range(self.size):
        for j in range(self.size):
            if self.arr[i][j] != self.maxNum:
                graph.append([i,j,self.arr[i][j]])
    
    dist = [self.maxNum] * (self.size)
    dist[startPoint] = 0
    flag = True
    for i in range(self.size - 1):
        flag = True
        for j in range(len(graph)):
            if dist[graph[j][1]] > dist[graph[j][0]] + graph[j][2]:
                dist[graph[j][1]] = dist[graph[j][0]] + graph[j][2]
                flag = False
        
        if flag:
            break
    
    flag = False
    for j in range(len(graph)):
        if dist[graph[j][1]] > dist[graph[j][0]] + graph[j][2]:
            flag = True
            
    return dist,flag

Floyd算法 (带权图、无权图、无负环、各个顶点之间的最短路径)

用一个新的数组来记录当前状态:

graph(i,j):表示从i到j的最短距离

graph(i,j) = min(graph(i,j) , graph(i,k) + graph(k,j)):表示从i -> k -> j 这条路比 i -> j 这条路短

1
2
3
4
5
6
7
8
def floyd(self):
    graph = self.arr.copy()
    for k in range(self.size):
        for i in range(self.size):
            for j in range(self.size):
                if i != j and graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph
,