图论模型：最小路径算法

基础理论

图，有向图，无向图的定义这里从略。

定义1 无环，无重边的图称为简单图。

定义2 任意两顶点均相邻的简单图称为完全图。含有n个顶点的完全图记为$K_n$

定义3 顶点的度：

（1）在无向图中，与顶点v关联的边的数目（环算两次）称为这个点的度，记为$d（v）$

（2）在有向图中，从顶点v引出的弧的数目称为v的v的出度，记为$d^+(v)$,从该点引入的弧的数目称为入度，记为$d^-(v)$,两者相加之和记为顶点的度。

定理1 对任意图，有

$$\sum d(v)=2 \cdot \left|E\right|$$

推论：任何图中的奇顶点总数为偶数.

图的矩阵表示

1.关联矩阵
对于无向图 ${G}$，其关联矩阵 ${M=(m_{ij}){n\times m}}$，其中

$$m{ij} = \begin{cases} 1, & \text{if } v_i \text{ is related to } e_j \\ 0, & \text{if } v_i \text{ is not related to } e_j \end{cases}$$

对于无向图${G}$其关联矩阵 ${M=(m_{ij}){n\times m}}$，其中

$$m_{ij} = \begin{cases} 1, & \text{当 } v_i \text{ 是起始点 } \\ 0, & \text{当 } v_i \text{ 与 } e_j \text{ 无关} \\ -1, & \text{当 } v_i \text{ 是末端点 } \\ \end{cases}$$

2.邻接矩阵

对于无向赋权图 ${G}$，其邻接矩阵 ${W=(m_{ij}){n\times m}}$，其中

$$w_{ij} = \begin{cases} \text{weight between } v_i \text{ and } v_j, & \text{顶点 } v_i \text{ 和 } v_j \text{ 相邻} \\ 0, & \text{顶点 } v_i \text{ 和 } v_j \text{ 不相邻} \end{cases}$$

对于有向赋权图，上式改为：

$$w_{ij} = \begin{cases} \text{weight between } v_i \text{ and } v_j, & (v_i,v_j) \in A \\ 0, & \text{顶点 } v_i \text{ 指向 } v_j \text{ 的弧不存在或}i=j \end{cases}$$

最短路算法

1.Dijkstra算法（贪心算法）
这是一种贪心算法，其主要用到的是迭代方法。它的依据是一个重要且明显的性质：最短路是一条路，它的任意子路也是该子路两端点间的最短路。
该算法的核心思想是：从起点由近及远地求得到各点的最短路和距离，直到到达某个顶点。
为了避免重复并保留每一步的计算信息，对于任意顶点$v_i$定义两个记号：

$$l(v):\text{顶点v的标号，表示起点到v点的当前路径长度} \\ z(v):\text{顶点v的父顶点标号，用于确定最短路线（类似于链表链域的作用）} \\ S_i: \text{表示具有永久标号的顶点集}$$

算法的操作可以这样表示：

令起点$u_0$：

$$l(u_0)=0,对v \neq u_0,\text{令}l(v)=∞,z(v)=u_0,S_0=\{u_0\},i=0.$$ $$对每个v \in \overline {S_i} (\overline{S_i}=V/S_i),\text{令}l(v)=min{l(v),l(v_{previous})+w(v_{previous}v)}$$

其中，$w_{uv}$表示顶点u和v之间边的权值.如果利用上一个节点对当前节点的$l(v)$进行了修改，则$z(v)=v_{previous}$
,否则$z(v)$不变.
计算$min\{l(v)\}$,把达到这个最小值的一个顶点即为$u_{i+1}$,令$S_{i+1}=S_i$
算法用伪代码表示如下：
Q = G.V // Q 是一个优先队列，按 $l(v)$排序

// 主循环
DIJKSTRA(G, w, s)
// 初始化
for each vertex v in G.V:
l(v) = ∞
z(v) = NIL
l(s) = 0
S_i =
while Q is not empty:
    u = EXTRACT-MIN(Q)  // 从 Q 中取出 l(v) 最小的顶点 u
    S_i = S_i ∪ {u}    // 将 u 加入永久标号集合 S_i
    for each vertex v in G.Adj[u]:  // 遍历 u 的所有邻接顶点 v
        if l(v) > l(u) + w(u, v):  // 松弛操作
            l(v) = l(u) + w(u, v)
            z(v) = u
            DECREASE-KEY(Q, v, l(v))  // 更新 Q 中 v 的优先级

下面是用python实现的算法：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典和父顶点字典
    l = {vertex: float('inf') for vertex in graph}
    z = {vertex: None for vertex in graph}
    l[start] = 0  # 起点的距离为0

    # 使用优先队列存储 (距离, 顶点) 对
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, u = heapq.heappop(priority_queue)

        # 如果当前距离大于已知最短距离，则跳过
        if current_distance > l[u]:
            continue

        # 遍历邻接顶点
        for v, weight in graph[u].items():
            distance = current_distance + weight

            # 如果发现更短路径，则更新
            if distance < l[v]:
                l[v] = distance
                z[v] = u
                heapq.heappush(priority_queue, (distance, v))

    return l, z

# 示例图的邻接表表示
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

l, z = dijkstra(graph, 'A')
print("最短距离:", l)
print("父顶点记录:", z)

2.Floid算法：（动态规划）

如果一个节点位于起点到重点的最短距离路径上，以节点0→8为例，

1. $$l（0→8）=l(0 \to 4)+l(4\to 8)(\text{if 4} \in \text{the shortest way }) \\ l（0→8）<l(0 \to 6)+l(6\to 8)(\text{if 6} \notin \text{the shortest way })$$
2. Python代码（片段）：

for k in range(self.V):
	for i in range(self.V):
		for j in range(self.V):
			if self.D[i][k]+self[k][j]<self.D[i][j]:
				self.D[i][j]=self.D[i][k]+self[k][j]
				self.S[i][j]=self.S[i][k]