• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Wyjaśnienie działania programu

VPS Starter Arubacloud
0 głosów
327 wizyt
pytanie zadane 18 maja 2016 w C i C++ przez Tommy Użytkownik (520 p.)
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;
}

 

1 odpowiedź

0 głosów
odpowiedź 18 maja 2016 przez niezalogowany
Jest coś czego dokładnie w nim nie rozumiesz, czy raczej ogólnie algorytmu?

Jeżeli to drugie to zaleciłbym skorzystać z gotowych wyjaśnień typu: http://everything.explained.today/Dijkstra's_algorithm/
komentarz 18 maja 2016 przez Tommy Użytkownik (520 p.)

Algorytm zrozumiałem, ale sposobu rozwiązania nie bardzo. nie za bardzo rozumiem co to jest:

if(shortestPath[v]==false && dist[v]<=min_value)
            min_value=dist[v], min_index=v;

co oznacza ten fragment kodu? Oraz druga nie zrozumiała rzecz to 

int minDistance(int dist[], bool shortestPath[])

co to w ogóle jest? że w deklaracji są inne dwie?
 Jestem nowy w temacie programowania :)

A! i jeszcze "bool", dlaczego bool?

komentarz 18 maja 2016 przez ribeiro Stary wyjadacz (11,440 p.)
Odnośnie drugiego, nie tyle dwie deklaracje wewnątrz, ale raczej zapowiedź, że takie właśnie dwa argumenty (w tym przypadku dwie tablice, jedna wypełniona typem int, druga typem bool) funkcja przyjmie i na nich będzie operować w momencie wywołania. Wywołanie następuje w linijce 48. Jako argumenty wrzucane są tam tablice zadeklarowane w linijce 35-36, a wypełnione pętlą w 41-42.

Podobne pytania

0 głosów
1 odpowiedź 387 wizyt
0 głosów
1 odpowiedź 162 wizyt
0 głosów
2 odpowiedzi 1,319 wizyt
pytanie zadane 4 sierpnia 2017 w C i C++ przez Jakub 0 Pasjonat (23,120 p.)

93,081 zapytań

142,045 odpowiedzi

321,464 komentarzy

62,427 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj

Wprowadzenie do ITsec, tom 2

Można już zamawiać tom 2 książki "Wprowadzenie do bezpieczeństwa IT" - będzie to około 650 stron wiedzy o ITsec (17 rozdziałów, 14 autorów, kolorowy druk).

Planowana premiera: 30.09.2024, zaś planowana wysyłka nastąpi w drugim tygodniu października 2024.

Warto preorderować, tym bardziej, iż mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy dodatkowe 15% zniżki! Dziękujemy zaprzyjaźnionej ekipie Sekuraka za kod dla naszej Społeczności!

...