Dijkstra最短路径算法的实现
内容提要
这篇文章介绍了Dijkstra算法在有向加权图中的应用。文章首先讲解了Dijkstra算法的局限性，然后介绍了有向加权图的表示方法和插入边的函数。接着详细介绍了使用Dijkstra算法找到最短路径的过程，包括使用set来获取最小距离节点和更新节点距离的方法。最后，文章给出了一个示例并打印了从源节点到每个节点的最短路径长度。
延伸解读
Dijkstra算法的适用边界
文章明确指出Dijkstra算法不适用于含负权边的图，也无法处理负权环，并且不能提供不可达节点的信息。这意味着在实际应用中，如果图中存在负权边，应选择Bellman-Ford等其他算法。此外，算法假设所有节点从源点可达，否则距离将保持为初始的INT_MAX。
有向图与无向图的统一处理
代码中的insertEdge函数通过isDirected参数同时支持有向图和无向图。对于无向图，每条边会以两个方向分别加入邻接表，从而将无向图视为双向有向图。这种设计使得同一套Dijkstra实现能直接用于两种图，但需注意无向图插入边时需传递isDirected为false。
使用set维护最小距离节点的技巧
算法使用set<pair<int,int>>来存储节点及其当前最短距离，利用set的有序性，begin()即为距离最小的节点。当发现更短路径时，需要先从set中删除旧的{距离,节点}对，再插入更新后的对。这避免了重复处理，但要求能准确找到旧条目，否则可能残留无效条目。
示例中的图与输出解读
示例构建了一个包含6个节点的无向加权图，源点为6。运行Dijkstra后，程序打印从源点到每个节点的最短距离。输出中索引0的距离为INT_MAX，因为节点编号从1开始，0号节点不存在。读者应注意节点编号与向量索引的对应关系，避免误读。
Q&A
Dijkstra算法的局限性是什么？
Dijkstra算法不适用于负权边的图，无法处理负循环的图，也无法提供不可达节点的信息。
如何表示有向加权图？
有向加权图使用邻接表表示，插入边的函数根据图的有向性进行处理。
Dijkstra算法是如何找到最短路径的？
Dijkstra算法通过使用集合获取最小距离节点，并更新节点距离，确保找到从源节点到每个节点的最短路径。
Dijkstra算法的实现中如何处理节点距离的更新？
在Dijkstra算法中，如果当前节点到邻居节点的距离小于已知的最短距离，则更新邻居节点的距离，并在集合中重新插入更新后的邻居节点。
Dijkstra算法适用于哪些类型的图？
Dijkstra算法适用于有向加权图，但不适用于包含负权边或负循环的图。
能否给出Dijkstra算法的示例？
示例中创建了一个有向加权图，并通过Dijkstra算法计算从源节点到每个节点的最短路径长度。
