Witam,
proszę o wytłumaczenie tego programu. Jest to algorytm Dijkstry.
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
int i;
int minDistance(int dist[], bool shortestPath[])
{
int INT_MAX;
int min_value=INT_MAX, min_index;
int v;
for (v=0; v<MAX; v++)
if(shortestPath[v]==false && dist[v]<=min_value)
min_value=dist[v], min_index=v;
return min_index;
}
int printSolution(int dist[], int n)
{
printf("A=0 B=1 C=2 D=3 E=4 \n\nWierzcholki Odleglosc od A (START)\n");
for (i=0; i<MAX; i++)
printf("\t%d \t\t\t %d\n", i, dist[i]);
}
void dijkstra(int graph[MAX][MAX], int src)
{
int INT_MAX;
int dist[MAX];
bool shortestPath[MAX];
int v;
int cyfra;
int u;
for (i=0; i<MAX; i++)
dist[i]= INT_MAX, shortestPath[i] = false;
dist[src] = 0;
for(cyfra=0; cyfra<MAX-1; cyfra++)
{
u=minDistance(dist, shortestPath);
shortestPath[u]=true;
for(v=0; v<MAX; v++)
if(!shortestPath[v] && graph[u][v] && dist[u] != INT_MAX && dist[u]+graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist, MAX);
}
int main()
{
int graph[MAX][MAX] = {
{ 0,100, 30, 0, 25},
{ 0, 0, 0, 0, 0},
{ 0, 17, 0, 7, 0},
{20, 0, 0, 0, 0},
{ 0, 18, 0, 0, 0}
};
dijkstra(graph, 0);
return 0;
}