用C写一下迪杰斯特拉算法
时间: 2023-04-01 08:01:54 浏览: 119
数据结构C语言版_迪杰斯特拉算法
好的,以下是用C语言实现迪杰斯特拉算法的代码:
```
#include <stdio.h>
#include <limits.h>
#define V 9
int minDistance(int dist[], bool sptSet[]) {
int min = INT_MAX, min_index;
for (int v = ; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
void printSolution(int dist[]) {
printf("Vertex \t Distance from Source\n");
for (int i = ; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}
void dijkstra(int graph[V][V], int src) {
int dist[V];
bool sptSet[V];
for (int i = ; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
dist[src] = ;
for (int count = ; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = ; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist);
}
int main() {
int graph[V][V] = {{, 4, , , , , , 8, },
{4, , 8, , , , , 11, },
{, 8, , 7, , 4, , , 2},
{, , 7, , 9, 14, , , },
{, , , 9, , 10, , , },
{, , 4, 14, 10, , 2, , },
{, , , , , 2, , 1, 6},
{8, 11, , , , , 1, , 7},
{, , 2, , , , 6, 7, }};
dijkstra(graph, );
return ;
}
```
希望这个回答对你有帮助!
阅读全文