有环图可以用Dijkstra求最短路吗

可以，Dijkstra算法可以用于求解图中带权重的最短路径问题，包括有环图。然而，有环图中存在负权边时，Dijkstra算法就无法正确地计算最短路径了。这是因为Dijkstra算法的核心思想是每次选择当前距离起点最近的节点来扩展，而在有环图中，存在负权边可能导致算法陷入循环。若要处理有环图的最短路径问题，可以使用其他算法，如Bellman-Ford算法或者Floyd-Warshall算法。

相关问题

dijkstra算法求一个最短路问题

Dijkstra算法是一种用于解决带权重图中的单源最短路径问题的算法，其中权重可以是负数，但不能存在负权重的环。该算法在使用中需要构建一个最短路径树，同时记录每个顶点到源节点的最短距离。

以下是Dijkstra算法的具体步骤：
1. 创建一个空的最短路径树，并将源节点添加进去。同时初始化每个节点的距离值为无穷大，源节点距离为0。
2. 遍历与源节点相连的所有节点，更新这些节点的距离值为与源节点相连边的权重值，并将这些节点添加到最短路径树中。
3. 从未加入最短路径树的节点中选择距离值最小的节点，并将其加入到最短路径树中。
4. 更新新加入节点相连的所有节点的距离值，如果更新后的距离值比原来的小，则更新它们的距离值。
5. 重复执行步骤3和步骤4，直到所有节点都加入到最短路径树中，或者找到了目标节点。

以下是Matlab代码实现Dijkstra算法，其中graph表示输入的邻接矩阵，start_node表示起始节点编号，end_node表示目标节点编号：

function [dist,path] = dijkstra(graph, start_node, end_node)
% 初始化dist和path
num_nodes = size(graph, 1);
dist = inf(num_nodes, 1);
path = zeros(num_nodes, 1);
visited = zeros(num_nodes, 1);

dist(start_node) = 0;
path(start_node) = -1;

% 迭代计算最短路径
for i=1:num_nodes
    % 选择未访问节点中距离最小的节点
    min_dist = inf;
    min_index = -1;
    for j=1:num_nodes
        if ~visited(j) && dist(j) < min_dist
            min_dist = dist(j);
            min_index = j;
        end
    end
    
    % 如果找不到可达节点，则退出
    if min_index == -1
        break;
    end
    
    % 更新dist和path
    visited(min_index) = 1;
    for j=1:num_nodes
        if graph(min_index,j) > 0 && ~visited(j)
            new_dist = dist(min_index) + graph(min_index,j);
            if new_dist < dist(j)
                dist(j) = new_dist;
                path(j) = min_index;
            end
        end
    end
    
    % 如果已经找到目标节点，则退出
    if min_index == end_node
        break;
    end
end

% 构建最短路径
if path(end_node) == 0
    path = [];
else
    path_nodes = [];
    current_node = end_node;
    while current_node ~= -1
        path_nodes = [path_nodes; current_node];
        current_node = path(current_node);
    end
    path = flip(path_nodes)';
end
end

poj 1125 最短路

题目描述

给定一张n个点的有向图，无自环，没有重边，每条边有一个时间和一个花费。求起点到终点的最短时间和最小花费。

输入格式

第一行一个正整数n，表示点数。

接下来nn行，每行n个整数，表示邻接矩阵，其中-1表示无边，其他数字表示边的时间。

再接下来一行，nn个整数，表示每条边的花费，其中-1表示这条边不存在。

输出格式

输出两个整数，分别表示最短时间和最小花费。

如果不存在从起点到终点的路径，输出-1 -1。

数据范围

1≤n≤100

输入样例1：

4
0 2 -1 5
-1 0 2 -1
-1 -1 0 3
-1 -1 -1 0
1 2 3 4

输出样例1：

7 6

输入样例2：

4
0 2 -1 5
-1 0 2 -1
-1 -1 0 3
-1 -1 -1 0
-1 -1 -1 -1

输出样例2：

-1 -1

算法1

(Dijkstra) $O(n^2)$

这道题是最短路模板题，可以使用Dijkstra算法求解。

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(Bellman-Ford) $O(n^3)$

这道题也可以使用Bellman-Ford算法求解。

时间复杂度

参考文献

C++ 代码