Dijkstra算法邻接矩阵实现下O(|V|²)时间复杂度的直观解释

嘿，我来给你直观拆解下为啥用邻接矩阵实现Dijkstra算法时时间复杂度是O(|V|²)哈～

我们的目标是用Dijkstra算法找出从起点s到图中所有其他顶点的最短路径。算法执行的每一步，都会记录各个顶点当前的最短距离值——你可以把这些值想象成一个表格。

比如拿7个节点的图举例，这个距离表就是7×7的大小。放到一般情况里，如果图有n个节点，那这个距离表就是n×n的规模。

要是换成完全图（任意两个不同顶点之间都有边），我们最多需要填充n(n-1)个表项（第一行是初始化的起点距离，不用额外计算）。你看，n(n-1)的量级其实就是O(n²)，对应到图里就是O(|V|²)，因为|V|就是节点数嘛。

这样是不是就把这个复杂度的由来讲清楚啦？

备注：内容来源于stack exchange，提问作者Mark