算法-最短路径长度

算法-贪心

1 最短路径长度

简介

给定一个n * n的矩阵M,其中 (i, j) 表示 i 到 j 的距离为M[i][j]
求start到各个点的最短路径长度

演示

0 999 10 999 30 100
999 0 5 999 999 999
999 999 0 50 999 999
999 999 999 0 999 10
999 999 999 20 0 60
999 999 999 999 999 0
(999表示无路可走)

以0为起点的最短路径长度是0 999 10 50 30 60

演示解析

0:0 -> 0
​ 0 + 0 = 0

1:0 -> 1
​ 0 + 999 = 999(无路可走)

2:0 -> 2
​ 0 + 10 = 10

3:0 -> 2 -> 3 || 0 -> 4 -> 3
​ 0 + 10 + 50 = 60 || 0 + 20 + 30 = 50

4:0 -> 4
​ 0 + 30 = 30

5:0 -> 2 -> 3 -> 5 || 0 -> 4 -> 3 -> 5
​ 0 + 10 + 50 + 10 = 70 || 0 + 20 + 30 + 10 = 60

思路

我们先把start到各点的路径长度当作最短路径长度,再找到其中的最小值Min,计算经过Min后的路径长度,和本来的长度比较,取出最小值.

其中我们还要一个标记向量vis,当 i 为最小值时,vis[i] 为 true,其后就不再更改.

实现

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
27
28
29
30
31
32
33
34
int FindMinIndex(vector<int> &v, vector<bool> &vis)
{
int MinIndex = 0;
while(vis[MinIndex] == true) //跳过已固定的路径长度
{ MinIndex++; }
for(int i = MinIndex + 1; i < v.size(); i++)
{
if(vis[i] == true) //跳过已固定的路径长度
{ continue; }
if(v[i] < v[MinIndex])
{ MinIndex = i; }
}
return MinIndex;
}
// Path[i][j]: i到j的路径长度
// Length[i]: start到i的最短路径长度
void Dijkstra(vector<vector<int>> &Paths, vector<int> &Length, int start)
{
vector<bool> vis(Paths.size(), false); //已固定标记
vis[start] = true;
int MinIndex;
Length = Paths[start]; //初始化最短路径长度
for(int i = 1; i < Paths.size(); i++)
{
MinIndex = FindMinIndex(Length, vis); //start到MinIndex最短
vis[MinIndex] = true; //标记
for(int j = 0; j < Length.size(); j++)
{
if(vis[j] == true) //跳过已固定的路径长度
{ continue; } //更新从start出发的最短路径长度
Length[j] = min(Paths[MinIndex][j] + Length[MinIndex], Length[j]);
}
}
}

END

本文就到这里了,接下来你可以自己写一个函数,求出怎么走是最短路径.