dijkstra算法c++
时间: 2023-10-18 12:14:45 浏览: 29
下面是Dijkstra算法的C++实现,假设给出了一个图的邻接矩阵:
```c++
#define INF 0x3f3f3f3f
#define MAXN 1000
int n; // 图中节点个数
int graph[MAXN][MAXN]; // 图的邻接矩阵表示
int dist[MAXN]; // 存储起点到每个节点的最短距离
bool visited[MAXN]; // 标记节点是否已被访问
void Dijkstra(int s)
{
memset(visited, false, sizeof(visited));
memset(dist, INF, sizeof(dist)); // 初始距离为INF
dist[s] = 0; // 起点到自己的距离为0
for(int i = 0; i < n; i++)
{
int u = -1; // 找到最短距离未确定的节点
for(int j = 0; j < n; j++)
if(!visited[j] && (u == -1 || dist[j] < dist[u]))
u = j;
visited[u] = true; // 标记节点已被访问
for(int v = 0; v < n; v++)
if(graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v]; // 更新最短距离
}
}
```
其中,`n`表示图中节点个数,`graph`表示图的邻接矩阵表示,`dist`存储起点到每个节点的最短距离,`visited`标记节点是否已被访问。
首先,将`visited`和`dist`数组初始化,`dist`数组初始距离为无穷大。然后,找到与起点距离最短的节点,并标记为已访问。对于每个未访问的节点,如果从起点到该节点的距离比已知的最短距离更短,就更新最短距离。重复以上步骤直到所有节点都已访问。
在这个实现中,我们用`-1`表示找不到最短距离未确定的节点,这是因为所有节点都已被访问。另外,邻接矩阵中`0`表示两个节点之间没有边相连。