C DERS 31: MULTI GRAPH

 

weighted-multigraph-300x172

Multi Graph – v3’ten v2’ye gidiş 2m fakat v2’den v3’e gidiş 1m

Komşuluk matrisi kullanılarak graph.komşuluk varsa 1 konulur.
Yönlü komşuluk matrisi ise gidilebiliyorsa 1 konulur.
Maliyetli graph(cost graph) kenarların(düğümleri bağlayan çizgi) uzunlukları farklıdır.
Tabloya uzaklıklar yazılır.
#include <stdio.h> 
#include <limits.h>
#include <stdlib.h>
#define NODES 8 //dijkstra algoritması

int graf[NODES][NODES] = { 0 };

void komsuyap(char x, char y,int cost)
{
	graf[x-'A'][y-'A'] = cost;
}

void listele()
{
	int i, j;
	printf("t");
	for (i = 0; i<NODES; i++)
	{
		printf("%ct", 'A' + i);
        //a dan başlayarak sütünların adını yazdırıyoruz
	}
	printf("n");
	for (i = 0; i<NODES; i++)
	{
		printf("%ct", 'A' + i);
		for (j = 0; j<NODES; j++)//j sütun
		{
			printf("%dt", graf[i][j]);
		}
		printf("n");
	}
	printf("n");
}

void dijkstra(int nereden, int nereye)
{
	char *ptr, ea[NODES]={0};
	int i, j, ead, ek;
	int ekm[NODES];
	char rota[NODES][255]={0};

	ekm[0] = 0;
	for (i = 0; i < NODES; i++) ekm[i] = INT_MAX;

	ead = nereden;
	for (i = 0; i < NODES; i++)
	{
		ek = INT_MAX;
		for (j = 1; j < NODES; j++)
		{
			if (!ea[j])
			{
				if (ekm[j] < ek)
				{
					ek = ekm[j];
					ead = j;
				}
			}
		}
		ea[ead] = 1;
		for  (j = 0; j < NODES; ++j)
		{
			if (!ea[j])
			{
				if (graf[ead][j] != 0)
				{
					if (ekm[j]> graf[ead][j] + ekm[ead])
					{
						ekm[j] = graf[ead][j] + ekm[ead];
						strcpy(rota[j], rota[ead]);
						ptr = rota[j];
						while (*ptr != NULL) ++ptr;
						*ptr = 'A' + ead;
					}
				}
			}
		}
	}

	printf("en kisa yol: %s%cn",rota[nereye],'A'+nereye);
}

int main(int argc, char *argv[])
{
	komsuyap('A','B',1);
	komsuyap('A','D',2);
	komsuyap('B','A',1);
	komsuyap('B','C',3);
	komsuyap('B','G',8);
	komsuyap('C','B',3);
	komsuyap('C','D',1);
	komsuyap('C','E',4);
	komsuyap('D','A',2);
	komsuyap('D','C',1);
	komsuyap('A','B',1);
	komsuyap('E','C',4);
	komsuyap('E','F',5);
	komsuyap('E','G',3);
	komsuyap('F','D',3);
	komsuyap('F','E',5);
	komsuyap('F','H',6);
	komsuyap('G','B',8);
	komsuyap('G','E',3);
	komsuyap('G','H',5);
	komsuyap('H','G',5);
	komsuyap('H','F',6);
	listele();
	dijkstra(0,6);

	return 0;
}