<commit_before>---
layout: post
category: Algorithms
title: 图最短路径
tags: Algorithms
---
floyd-warshall for k, for i , for j. 更新a[i][j]

bellman-ford n-1次relax, 每次relax遍历所有边， 对<u, v>, d[v] = min(d[v], d[u] + weight), 最后判断是否有个边存在d[v] > d[u] + weight即有负边O(V*E)

## Dijkstra
求的是单源到其他节点的最短路径，需要权值非负

**为什么不能处理负权边？**

可能出现这样一种情况：因为dijktra算法每次都先寻找前往节点的最小值（正数），并将节点加入已访问集合之中，之后不再对其进行更新。

举个例子，目标：寻找A-C的最短路径。使用Dijkstra算法时，比较从A->B和A->C的开销，显然A->C的更小，于是选择到C的路径，并将C处理成处理过的节点。到这里发现了什么问题呢，A->B->C不是更短吗？就是负权边的情况。

![](https://cdn.jsdelivr.net/gh/mafulong/mdPic@master/images/fb9007f16f653cdb5634d0ef29f83f79.jpeg)

时间复杂度

	Complexity is
	O( (|E|+|V|)log|V| ) 
  一半可以理解为O(VlogV)<commit_msg>add logbook<commit_after>---
layout: post
category: Algorithms
title: 图最短路径
tags: Algorithms
---
floyd-warshall for k, for i , for j. 更新a[i][j]

bellman-ford n-1次relax, 每次relax遍历所有边， 对<u, v>, d[v] = min(d[v], d[u] + weight), 最后判断是否有个边存在d[v] > d[u] + weight即有负边O(V*E)



bellman-ford可以解决 有向无环图中边的权值为负数的情况，但是dijkstra不能解决负权值的问题。

dag图其实额可以用拓扑排序+树形dp做。dp[v] = min(dp[u]+1)

大家想一想拓扑排序的规则：不断的寻找入度为0的节点，那么入度为0的节点代表什么呢，入度为0的节点说明在它入度变为0之前，所有指向它的节点已经通过邻接关系访问过它，也就是说，如果以拓扑排序访问的顺序来计算最短路径的话，那么给定一个节点，只有在拓扑排序顺序排在它之前的节点才有边指向这个节点，排在它之后的就可以忽略掉了，这样就节省了遍历的时间，而且保证不会漏掉任何一个指向它的节点。在遍历到这个节点之前，就已经计算好某个节点，到这个节点的单源最短路值。这就是应用拓扑排序的最大精妙之处。
————————————————
版权声明：本文为CSDN博主「yingsun」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/zzran/article/details/8926295

## Dijkstra
求的是单源到其他节点的最短路径，需要权值非负

**为什么不能处理负权边？**

可能出现这样一种情况：因为dijktra算法每次都先寻找前往节点的最小值（正数），并将节点加入已访问集合之中，之后不再对其进行更新。

举个例子，目标：寻找A-C的最短路径。使用Dijkstra算法时，比较从A->B和A->C的开销，显然A->C的更小，于是选择到C的路径，并将C处理成处理过的节点。到这里发现了什么问题呢，A->B->C不是更短吗？就是负权边的情况。

![](https://cdn.jsdelivr.net/gh/mafulong/mdPic@master/images/fb9007f16f653cdb5634d0ef29f83f79.jpeg)

时间复杂度

	Complexity is
	O( (|E|+|V|)log|V| ) 
  一半可以理解为O(VlogV)
{'fraction_non_alphanumeric': 0.1615553121577218, 'fraction_numerical': 0.03066812705366922, 'mean_word_length': 8.0, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 17, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2885990', 'n_tokens_mistral': 1375, 'n_tokens_neox': 1504, 'n_words': 92}