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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
#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; } |