Алгоритм Дейкстры с: как работает, примеры реализации и применение
Алгоритм Дейкстры – это алгоритм поиска кратчайших путей во взвешенном графе. Он может быть использован для нахождения кратчайшего пути между двумя вершинами графа, а также для нахождения кратчайшего пути от одной вершины до всех остальных. Алгоритм работает для графов без отрицательных весов ребер.
Алгоритм состоит в следующих шагах:
1. Задаем стартовую вершину и вес 0. Остальным вершинам присваиваем максимальный вес (бесконечность).
2. Из стартовой вершины находим все смежные вершины и запоминаем их вместе с их весами.
3. Из найденных смежных вершин выбираем вершину с наименьшим весом и помечаем ее как пройденную.
4. Для каждой непройденной вершины, смежной с выбранной на шаге 3, ищем путь через выбранную вершину, и если этот путь короче, то обновляем вес.
5. Повторяем шаги 3 и 4, пока все вершины не будут помечены как пройденные.
Пример кода на языке C:
#include
#include
#define INF 9999
#define MAX 10
void dijkstra(int graph[MAX][MAX], int n, int start);
int main()
{
int graph[MAX][MAX], i, j, n, start;
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("Enter the adjacency matrix:\n");
for(i=0; i { for(j=0; j { scanf("%d", &graph[i][j]); } } printf("Enter the starting vertex: "); scanf("%d", &start); dijkstra(graph, n, start); return 0; } void dijkstra(int graph[MAX][MAX], int n, int start) { int cost[MAX][MAX], distance[MAX], visited[MAX], count, i, j, minDistance, nextNode; //заполнить матрицу смежности и матрицу стоимости for(i=0; i { for(j=0; j { if(graph[i][j]==0) { cost[i][j]=INF; } else { cost[i][j]=graph[i][j]; } } } //инициализация массивов visited и distance for(i=0; i { distance[i]=cost[start][i]; visited[i]=0; } distance[start]=0; visited[start]=1; count=1; while(count { minDistance=INF; //выбор ближайшей вершины for(i=0; i { if(distance[i] { minDistance=distance[i]; nextNode=i; } } //пометка выбранной вершины visited[nextNode]=1; //обновление distance[] for(i=0; i { if(!visited[i]) { if(minDistance+cost[nextNode][i] { distance[i]=minDistance+cost[nextNode][i]; } } } count++; } //вывод кратчайших расстояний printf("\nShortest distances from %d:\n", start); for(i=0; i { if(i!=start) { printf("From %d to %d: %d\n", start, i, distance[i]); } } } В данном примере пользователь должен ввести матрицу смежности и номер стартовой вершины, после чего алгоритм Дейкстры находит кратчайшие расстояния от стартовой вершины до всех остальных. Выводится список всех кратчайших расстояний.