用C++ 编写一个简单的程序，实现单源最短路径问题，并给出一个矩阵样例

在C++中，我们可以使用Dijkstra算法来解决单源最短路径问题。这是一个经典的图论问题，通常用于找出从一个节点到其他所有节点的最短路径。下面是一个简化的Dijkstra算法示例，它假定输入是一个邻接矩阵表示的无权有向图：

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

// 定义距离无穷大
const int INF = std::numeric_limits<int>::max();

void dijkstra(std::vector<std::vector<int>>& graph, int start) {
    int n = graph.size(); // 图的顶点数

    std::vector<int> dist(n, INF); // 初始化距离数组，所有节点的距离设为无穷大
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq; // 小根堆，保存待处理的节点及其距离

    dist[start] = 0; // 起始节点的距离设为0
    pq.push({0, start}); // 把起始节点加入队列

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        
        // 遍历u的所有邻居
        for (int v = 0; v < n; ++v) {
            if (graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) { // 如果从u到v的距离更短
                dist[v] = dist[u] + graph[u][v]; // 更新v的最短距离
                pq.push({dist[v], v}); // 把更新后的v加入队列
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        std::cout << "Node " << i << " to Start: Distance " << dist[i] << std::endl;
    }
}

int main() {
    // 示例矩阵，其中0表示不存在边，正整数表示边的权重
    std::vector<std::vector<int>> graph = {
        {0, 4, 0, 0},
        {2, 0, 1, 5},
        {0, 8, 0, 7},
        {9, 1, 0, 0}
    };

    dijkstra(graph, 0); // 以节点0为起点计算最短路径
    return 0;
}

在这个例子中，`graph`是一个二维数组，代表了节点间的连接以及它们之间的成本。`dijkstra`函数首先初始化每个节点的最短距离为无限大，然后使用小根堆维护未确定最短路径的节点。每次从队列中取出距离当前最小的节点，更新其邻居的最短距离。

运行此程序，你会看到从起点0出发，到其他每个节点的最短路径长度。