简述最短路问题的模型和算法思路

最短路问题是指在一个加权有向图中，求出其中一点到其他所有点的最短路径。最短路径可以用路径上所有边的权值之和来衡量。

常用的算法有 Dijkstra 算法和 Bellman-Ford 算法：

Dijkstra 算法：

1. 初始化，将起点到自己的距离设为 0，其他所有点到起点的距离设为无穷大。

2. 选取一个未确定最短路径的节点，设其到起点的距离为当前确定的最短路径长度加上该节点到起点的距离。

3. 遍历该节点的所有出边，如果该出边能够使到达另一个节点的距离变小，则更新该节点的距离。

4. 重复执行步骤2和步骤3，直到所有节点的最短路径都被确定。

Bellman-Ford 算法：

1. 初始化，将起点到自己的距离设为 0，其他所有点到起点的距离设为无穷大。

2. 重复执行以下步骤，直到所有节点的最短路径都被确定：

a. 遍历所有边，如果该边能够使到达另一个节点的距离变小，则更新该节点的距离。

3. 如果在步骤2中没有发现任何可更新的距离，则算法结束。

Dijkstra 算法适用于稠密图，时间复杂度为 O(n^2) 或者 O(mlogn)，其中 n 是节点数，m 是边数。Bellman-Ford 算法适用于稀疏图，时间复杂度为 O(nm)，其中 n 是节点数，m 是边数。