请举例用dijkstra贪心求解过程
时间: 2023-10-20 15:05:19 浏览: 20
假设我们有下面这个图:
```
1
/ | \
2 3 4
/ \ / \
5 6 7 8
```
其中数字代表节点,我们需要从节点1出发到达所有其他节点,每条边上的数字表示它们的距离。现在我们使用Dijkstra算法来解决这个问题。
1. 首先,我们将起点1标记为已访问,将起点与其它节点的距离初始化为无穷大,将起点到自己的距离设为0。
```
visited = [1]
distance = [0, inf, inf, inf, inf, inf, inf, inf]
```
2. 然后,我们遍历起点的邻居,更新它们到起点的距离。
```
visited = [1, 2, 3, 4]
distance = [0, 1, 2, 3, inf, inf, inf, inf]
```
3. 接着,我们找到距离起点最近的节点2,将其标记为已访问,然后遍历其邻居,更新它们到起点的距离。
```
visited = [1, 2, 3, 4, 5, 6]
distance = [0, 1, 2, 3, 6, 7, inf, inf]
```
4. 然后,我们找到距离起点最近的节点5,将其标记为已访问,然后遍历其邻居,更新它们到起点的距离。
```
visited = [1, 2, 3, 4, 5, 6, 7]
distance = [0, 1, 2, 3, 6, 7, 10, inf]
```
5. 接下来,我们找到距离起点最近的节点3,将其标记为已访问,然后遍历其邻居,更新它们到起点的距离。
```
visited = [1, 2, 3, 4, 5, 6, 7, 8]
distance = [0, 1, 2, 3, 6, 7, 10, 11]
```
6. 最后,我们找到距离起点最近的节点4,将其标记为已访问。由于所有节点都已被访问,我们得到了每个节点到起点的最短距离。
因此,从节点1出发到达所有其他节点的最短距离为:
```
1 -> 2: 1
1 -> 3: 2
1 -> 4: 3
1 -> 5: 6
1 -> 6: 7
1 -> 7: 10
1 -> 8: 11
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)