dijkstra算法求最短路径cMATLAB

Dijkstra算法是一种经典的最短路径算法，它可以用来求解一个带权重的有向图或者无向图的最短路径问题。其基本思想是从源点出发，不断扩展当前已经找到的最短路径集合，直到找到源点到终点的最短路径为止。

在C语言和MATLAB中实现Dijkstra算法主要需要以下步骤：

1. 初始化：将源点到每个点的距离初始化为正无穷，源点到自身的距离为0。

2. 选取当前距离源点最近的一个点，将其加入到已经找到最短路径的集合中。

3. 根据新加入的点更新源点到其他点的距离。如果新加入的点可以使得某个点到源点的距离变小，则更新这个点到源点的距离。

4. 重复执行2和3，直到所有点都被加入到已经找到最短路径的集合中。

最后，根据每个点到源点的距离，即可求出源点到每个点的最短路径。

以下是一个简单的C语言实现示例（假设图用邻接矩阵表示）：

#define MAX_SIZE 100
#define INF 999999

void dijkstra(int n, int start, int graph[MAX_SIZE][MAX_SIZE], int dist[]) {
    bool visited[MAX_SIZE] = { false };
    for (int i = 0; i < n; i++) {
        dist[i] = graph[start][i];
    }
    visited[start] = true;
    for (int i = 0; i < n - 1; i++) {
        int min_dist = INF;
        int min_index = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_index = j;
            }
        }
        if (min_index == -1) {
            break;
        }
        visited[min_index] = true;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[min_index] + graph[min_index][j] < dist[j]) {
                dist[j] = dist[min_index] + graph[min_index][j];
            }
        }
    }
}

以下是一个简单的MATLAB实现示例（假设图用邻接矩阵表示）：

function [dist] = dijkstra(n, start, graph)
    visited = false(1, n);
    dist = graph(start, :);
    visited(start) = true;
    for i = 1:n-1
        [~, min_index] = min(dist(~visited));
        if isempty(min_index)
            break
        end
        min_index = find(~visited, 1) - 1 + min_index;
        visited(min_index) = true;
        dist(~visited) = min(dist(~visited), dist(min_index) + graph(min_index, ~visited));
    end
end