dijkstra算法c++示例
时间: 2023-11-06 09:56:48 浏览: 119
可以为您提供一个简单的 Dijkstra 算法的 C 示例代码:
```c
#include <stdio.h>
#include <limits.h>
#define VERTICES 6
int graph[VERTICES][VERTICES] = {
{0, 2, 5, 1, INT_MAX, INT_MAX},
{2, 0, 3, 2, INT_MAX, INT_MAX},
{5, 3, 0, 3, 1, 5},
{1, 2, 3, 0, 1, INT_MAX},
{INT_MAX, INT_MAX, 1, 1, 0, 2},
{INT_MAX, INT_MAX, 5, INT_MAX, 2, 0}
};
int dijkstra(int start, int end) {
int dist[VERTICES];
int visited[VERTICES] = {0};
int i, j, min, index;
for (i = 0; i < VERTICES; i++) {
dist[i] = graph[start][i];
}
visited[start] = 1;
for (i = 0; i < VERTICES - 1; i++) {
min = INT_MAX;
for (j = 0; j < VERTICES; j++) {
if (!visited[j] && dist[j] < min) {
min = dist[j];
index = j;
}
}
visited[index] = 1;
for (j = 0; j < VERTICES; j++) {
if (!visited[j] && dist[index] + graph[index][j] < dist[j]) {
dist[j] = dist[index] + graph[index][j];
}
}
}
return dist[end];
}
int main() {
int start = 0, end = 5;
int shortest_path = dijkstra(start, end);
printf("Shortest path between vertex %d and vertex %d is: %d", start, end, shortest_path);
return 0;
}
```
该代码演示了一个有向加权图的 Dijkstra 算法实现。其中,`graph` 数组表示图的邻接矩阵,`dijkstra` 函数返回从起点到终点的最短路径长度。