dijkstras algorithm in matlab

main.m
function [dist, path] = dijkstra(graph, start_node, end_node)
% DIJKSTRA finds the shortest path between two nodes in a graph.
% INPUTS:
% graph: adjacency matrix representing the graph
% start_node: the starting node index
% end_node: the ending node index
% OUTPUTS:
% dist: the total distance of the shortest path from start_node to end_node
% path: the shortest path from start_node to end_node

n = size(graph, 1); % number of nodes in graph
dist = inf(1, n); % initialize distance to all nodes as infinity
dist(start_node) = 0; % except to the starting point, which is zero
visited = zeros(1, n); % initialize visited nodes to zero
path = zeros(1, n); % initialize path to all zeros
for i = 1:n-1
    u = find(visited == 0 & dist == min(dist)); % choose the node with the shortest distance
    u = u(1); % in case of multiple nodes with the same shortest distance
    visited(u) = 1; % mark the node as visited
    for v = 1:n
        if graph(u, v) ~= 0 % if there's an edge (u,v)
            alt = dist(u) + graph(u, v); % calculate the alternative distance
            if alt < dist(v) % if it's shorter than the current distance, update
                dist(v) = alt;
                path(v) = u;
            end
        end
    end
end

% construct path
path_list = end_node;
n = end_node;
while n ~= start_node
    n = path(n);
    path_list(end+1) = n;
end
path_list = fliplr(path_list);
path = path_list;

end
1424 chars
42 lines

main.m
graph = [0 2 0 0 0 0 0;
         2 0 1 3 0 0 0;
         0 1 0 2 1 0 0;
         0 3 2 0 0 2 0;
         0 0 1 0 0 1 1;
         0 0 0 2 1 0 1;
         0 0 0 0 1 1 0];
         
[start_node, end_node] = [1, 6];
[dist, path] = dijkstra(graph, start_node, end_node)

% expected output:
% dist = 3
% path = [1 2 3 4 6]
317 chars
15 lines