c++ örnek en kısa yol greedy algoritması

Greedy yaklaşımı, graf üzerinde belirli bir konuda optimum sonucu veya en iyi sonucu bulabilmek amacıyla dolaşma yapılırken bir sonraki düğümü belirlemek için kullanılan bir karar verme yöntemidir. Greedy yaklaşımında o andaki seçenekler içerisinden en iyi olarak görünen seçilir. Greedy yönlü ve maliyetli graflarda kullanılır.
Örnek olarak 5 düğümlü bir graf 5x5 komşuluk matrisi şeklinde gösterilsin. Grafın şekli dizide gösterilmiştir.

#include<iostream>
#define N 5
#define EBAS 0x7FFFFFFF
using namespace std;

int maliyethesapla();
int GRAF[N][N]={ -1, 2, -1, -1, 5,
                 -1, -1, 1, 4, 2,
                 1, -1, -1, -1, 4,
                 12, -1, -1, -1, -1,
                 -1, -1, -1, 3, -1
               };

int EKM[N];
int main()
{
    int i;
    maliyethesapla();
    for (i=0;i<N;i++)
        cout<<EKM[i]<<" ";
    return 0;
}

int maliyethesapla()
{
    char ELEALINDI[N]={0};
    int i, j, ead, enkucuk;
    for (i=1;i<=N;i++)
        EKM[i]=EBAS;
    EKM[0]=0;
    ead=0;
    for (i=0;i<N;i++)
    {
        for (j=0;j<N;j++)
            if (!ELEALINDI[j])
                if (GRAF[ead][j]!=-1)
                    if (EKM[j]>GRAF[ead][j]+EKM[ead])
                        EKM[j]=GRAF[ead][j]+EKM[ead];
        enkucuk=EBAS;
        for (j=1;j<N;j++)
            if (!ELEALINDI[j])
                if (EKM[j]<enkucuk)
                {
                    enkucuk=EKM[j];
                    ead=j;
                }
        ELEALINDI[ead]=1;
    }
}

Kaynak: Algoritma Geliştirme ve Veri Yapıları
Dr. Rıfat Çölkesen