Hi, Can anyone help me how to read csv file to find shortest path using dijkstra's algorithm. Thank you.

I tried the program suggested before in this forum. works well. but at the same time, could anyone help me how to read the input from csv file to get the shortest path.

Thank you.

Answer 1

[Ayush]

Hi @JEBASINGH KIRUBAKARAN,

I understand you need to take input data from CSV file and find the shortest distance using Dijkstra's algorithm.

Here is the basic workflow for the same:

1. Read the graph data from the CSV file. For reading the data, you can use “readtable” function. For more information on this, you can refer here: https://www.mathworks.com/help/matlab/ref/readtable.html
2. Convert the nodes to numeric indices (since MATLAB's Dijkstra algorithm works with numerical node identifiers). You can map node names to numeric indices using “containers.Map”, as MATLAB’s Dijkstra implementation works with numeric indices. For more information on this, you can refer here: https://www.mathworks.com/help/matlab/ref/containers.map.html
3. Now, try to build an adjacency matrix. For more information on adjacency matrix, you can refer here: https://www.mathworks.com/help/matlab/ref/graph.adjacency.html
4. Use MATLAB’s built-in “shortestpath” or “Dijkstra” method to compute the shortest path. For more information on “Dijkstra”, you can refer the following file exchange: https://www.mathworks.com/matlabcentral/fileexchange/36140-dijkstra-algorithm. For more information on “shortestpath” function, you can refer here: https://www.mathworks.com/help/matlab/ref/graph.shortestpath.html

Here is the pseudo MATLAB code for Dijkstra algorithm for your reference:

function [path, distance] = dijkstra(adj_matrix, source_idx)
    n = size(adj_matrix, 1);
    distance = Inf(1, n);
    distance(source_idx) = 0; 
    visited = false(1, n);
    previous = NaN(1, n);
    
    for i = 1:n
        [~, u] = min(distance .* ~visited + Inf(1, n) .* visited);
        visited(u) = true;
        
        for v = 1:n
            if adj_matrix(u, v) < Inf && ~visited(v)
                alt = distance(u) + adj_matrix(u, v);
                if alt < distance(v)
                    distance(v) = alt;
                    previous(v) = u;
                end
            end
        end
    end

    path = {};
    current = source_idx;
    while ~isnan(previous(current))
        path = [current, path];
        current = previous(current); 
    end
    % Return the shortest distance and path
end

Hope it helps!

[JEBASINGH KIRUBAKARAN]

Thank you Ayush