图论问题集合

单源最短路问题德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪!!!他们的德克萨斯长角牛吃起来不错,可是它们并不是很擅长生产富含奶油的乳制品。农夫John此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任,以减轻德克萨斯人忍受酷暑的痛苦。John已经研究过可以把牛奶从威斯康星运送到德克萨斯州


迪杰斯特拉(dijkstra)算法

迪杰斯特拉算法适用范围:处理权值为正的最短路问题步骤:初始化d[1]=0,其他d[n]=INT_MAXs中放入已经确定最短路的点遍历,把不在s中的距离最近的点,加入到s更新所有点的距离给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为正值。请你求出 1 号点到 n 号点的最短


Bellman-Ford算法

Bellman-Ford算法适用范围:处理权值带负数的,且有边数限制的最短路问题给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离,如果无法从 1 号点走到 n 号点,输出 impossible。注意:图中可