MATLAB利用dijkstra求最短路径c

MATLAB中可以利用Graph对象和shortestpath函数实现Dijkstra算法求解最短路径。以下是一个简单的示例代码：

% 创建一个有向图对象
G = digraph([1 2 2 3 3 4 4 5 5 6],[2 3 4 4 5 5 6 4 6 5]);

% 设置边权重
G.Edges.Weight = [3 1 5 2 7 1 6 3 2 7];

% 使用shortestpath函数求解1到6的最短路径
path = shortestpath(G, 1, 6);

% 输出最短路径和权重
disp(path);
disp(sum(G.Edges.Weight(findedge(G,path(1:end-1),path(2:end)))));

在上述代码中，我们创建了一个有向图对象，并设置了边权重。然后利用shortestpath函数求解1到6的最短路径，并输出结果。注意，最短路径的权重需要通过findedge函数和sum函数计算得到。

相关问题

MATLAB利用dijkstra求最短路径c的完整运算过程及代码

下面是一个完整的MATLAB代码，使用Dijkstra算法求解最短路径问题：

% 构造邻接矩阵
% 这里使用一个6个点的图作为例子
% 0表示两个点之间没有边相连
% 对角线上的元素都为0，表示一个点到自己的距离为0
W = [0 3 0 0 4 0;
     3 0 5 0 7 0;
     0 5 0 2 0 1;
     0 0 2 0 6 0;
     4 7 0 6 0 2;
     0 0 1 0 2 0];

start_node = 1; % 起点为1
end_node = 6;   % 终点为6

n = length(W);  % 计算节点数

visited = zeros(1, n);  % 标记节点是否被访问过
distance = ones(1, n) * inf;  % 存储起点到每个节点的最短距离
pre_node = zeros(1, n);  % 存储每个节点的前驱节点

distance(start_node) = 0;  % 起点到自己的距离为0

% Dijkstra算法
for i = 1:n
    % 找到当前未访问节点中距离起点最近的节点
    min_distance = inf;
    for j = 1:n
        if ~visited(j) && distance(j) < min_distance
            min_distance = distance(j);
            current_node = j;
        end
    end
    
    % 标记该节点为已访问
    visited(current_node) = 1;
    
    % 更新与当前节点相邻的节点的距离
    for j = 1:n
        if ~visited(j) && W(current_node, j) ~= 0 && distance(current_node) + W(current_node, j) < distance(j)
            distance(j) = distance(current_node) + W(current_node, j);
            pre_node(j) = current_node;
        end
    end
end

% 输出最短路径和距离
if isinf(distance(end_node))
    disp('起点和终点之间没有路径');
else
    path = [end_node];
    while path(1) ~= start_node
        path = [pre_node(path(1)), path];
    end
    disp(['最短路径为：', num2str(path)]);
    disp(['最短距离为：', num2str(distance(end_node))]);
end

在上面的代码中，我们首先构造了一个邻接矩阵W表示图中各个节点之间的距离。然后设置起点和终点，并初始化visited、distance和pre_node数组。接下来就是Dijkstra算法的核心部分，我们使用两个循环来实现。

第一个循环用于找到当前未访问节点中距离起点最近的节点。我们首先将所有未访问节点的距离都设为无穷大，然后遍历所有未访问节点，找到距离起点最近的节点。找到最近节点后，我们将其标记为已访问。

第二个循环用于更新与当前节点相邻的节点的距离。具体来说，我们遍历所有未访问节点，如果当前节点和该节点之间有边相连，且当前节点到起点的距离加上该边的距离小于该节点到起点的距离，那么就更新该节点的距离和前驱节点。最终得到的distance数组就是起点到各个节点的最短距离，pre_node数组则记录了每个节点的前驱节点。

最后，我们根据pre_node数组回溯得到最短路径和距离，并输出结果。

用matlab实现dijkstra算法求最短路径

Dijkstra算法是一种用于计算加权图的最短路径的算法。下面是用MATLAB实现Dijkstra算法的示例代码。

function [dist, path] = dijkstra(graph, start, dest)
%DIJKSTRA Calculates the shortest path in a graph using Dijkstra's algorithm
%   [DIST, PATH] = DIJKSTRA(GRAPH, START, DEST) calculates the shortest path
%   in the graph GRAPH from node START to node DEST using Dijkstra's algorithm.
%   DIST is the distance of the shortest path and PATH is a vector of node
%   indices representing the path from START to DEST.
%
%   GRAPH is an N x N matrix representing the adjacency matrix of the graph
%   where N is the number of nodes in the graph. The element GRAPH(i,j) is the
%   weight of the edge from node i to node j. If there is no edge from node i
%   to node j, then GRAPH(i,j) should be set to Inf.
%
%   START and DEST are scalar values representing the starting and ending nodes
%   of the path to be found.

% Initialize the distance vector and the visited set
dist = Inf(size(graph, 1), 1);
visited = false(size(graph, 1), 1);

% Set the distance to the starting node to 0
dist(start) = 0;

% Loop until the destination node is visited
while ~visited(dest)
    % Find the node with the minimum distance
    [~, idx] = min(dist(~visited));
    if isempty(idx)
        error('No path exists from start to destination');
    end
    curr = find(~visited, idx(1), 'first');

    % Update the distances to the neighbors of the current node
    neighbors = find(graph(curr, :) ~= Inf);
    for i = 1:length(neighbors)
        node = neighbors(i);
        if ~visited(node)
            alt = dist(curr) + graph(curr, node);
            if alt < dist(node)
                dist(node) = alt;
                path(node) = curr;
            end
        end
    end

    % Mark the current node as visited
    visited(curr) = true;
end

% Reconstruct the path
path = dest;
while path(1) ~= start
    path = [path(1), path];
    path(1) = path(2);
    path(2) = path(3);
end
path = [start, path];
end

这个函数接受一个邻接矩阵作为输入，该矩阵表示图的结构，以及起点和终点。返回值是两个向量，一个是最短距离，另一个是路径。可以使用以下代码来测试函数：

graph = [Inf, 2, 3, Inf, Inf;
         2, Inf, 4, 1, Inf;
         3, 4, Inf, 1, 5;
         Inf, 1, 1, Inf, 2;
         Inf, Inf, 5, 2, Inf];
[start, dest] = deal(1, 5);
[dist, path] = dijkstra(graph, start, dest);
fprintf('Shortest distance from node %d to node %d: %d\n', start, dest, dist(dest));
fprintf('Path from node %d to node %d: %s\n', start, dest, num2str(path));

这段代码将输出从节点1到节点5的最短距离和路径。