在计算机科学中，Dijkstra算法是一种用于解决带权有向图中单源最短路径问题的贪心算法。这种算法由荷兰计算机科学家艾兹格·迪杰斯特拉于1956年发明，它使用广度优先搜索策略来解决问题。

算法原理

Dijkstra算法的基本思想是：从源点开始，逐步向外层扩展，直到找到从源点到所有其他顶点的最短路径。

算法步骤：

1. 初始化距离数组dist，其中dist[i]表示从源点到顶点i的最短距离。源点到自身的距离设为0，到其他顶点的距离设为无穷大。
2. 创建一个集合S，存放已经找到最短路径的顶点。初始时，S为空集。
3. 从所有未加入S的顶点中，选择dist值最小的顶点u，将其加入S。
4. 更新u的所有邻接点的dist值。如果通过u到达某个邻接点的距离比当前dist值更小，则更新该邻接点的dist值。
5. 重复步骤3和4，直到所有顶点都加入S。

C++实现

以下是使用C++实现Dijkstra算法的示例代码。假设图以邻接矩阵的形式表示，其中graph[i][j]表示从顶点i到顶点j的边的权重，如果i和j之间没有边，则graph[i][j]为无穷大。

```cpp

include

include

include

using namespace std;

const int INF = numeric_limits::max();

void dijkstra(const vector>& graph, int source, vector& dist) {
int numVertices = graph.size();
vector visited(numVertices, false);

for (int i = 0; i < numVertices; ++i) {
    dist[i] = INF;
}
dist[source] = 0;
for (int i = 0; i < numVertices - 1; ++i) {
    int u = -1;
    int minDist = INF;
    for (int j = 0; j < numVertices; ++j) {
        if (!visited[j] && dist[j] <= minDist) {
            u = j;
            minDist = dist[j];
        }
    }
    visited[u] = true;
    for (int v = 0; v < numVertices; ++v) {
        if (!visited[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
            dist[v] = dist[u] + graph[u][v];
        }
    }
}

}

int main() {
vector> graph = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};

int source = 0;