C语言采用邻接矩阵存储,实现迪杰斯特拉算法;若规定图中若干个路径必经点,再在原来的基础上改进迪杰斯特拉算法
时间: 2023-08-31 22:24:46 浏览: 60
邻接矩阵存储的图可以使用迪杰斯特拉算法求解最短路径。如果规定图中若干个路径必经点,则可以考虑使用修改后的迪杰斯特拉算法。
修改后的算法主要思路是在原有的最短路径算法中增加对必经点的处理。具体实现步骤如下:
1. 将必经点标记出来,标记的方法可以是将其权值设为0。
2. 修改迪杰斯特拉算法中的松弛操作,即当松弛边时,如果边的起点或终点是必经点,则需要考虑是否需要更新最短路径。
3. 在算法结束后,判断是否经过了所有的必经点,如果有未经过的必经点,则说明不存在符合要求的最短路径。
下面是修改后的迪杰斯特拉算法的伪代码实现:
```
Dijkstra(G, s, t, P)
for each vertex v in G
dist[v] = inf
prev[v] = null
dist[s] = 0
Q = vertices(G)
while Q is not empty
u = vertex in Q with min dist[u]
remove u from Q
for each neighbor v of u
alt = dist[u] + weight(u, v)
if alt < dist[v]
dist[v] = alt
prev[v] = u
if v is a required point
for each neighbor w of v
if w is not a required point
alt2 = alt + weight(v, w)
if alt2 < dist[w]
dist[w] = alt2
prev[w] = v
if prev[t] is null
return "no path"
path = []
u = t
while prev[u] is not null
path.push(u)
u = prev[u]
path.push(s)
return path.reverse()
```
其中,P为必经点的集合,weight(u, v)表示边(u, v)的权值。
注意,这只是一种实现方式,具体实现还需要考虑更多细节。
相关推荐
![](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)