Aşağıdaki eğitim bize Dijkstra'nın En Kısa Yol Algoritmasını öğretecek. Dijkstra Algoritmasının çalışmasını adım adım grafiksel anlatımla anlayacağız.

Aşağıdakileri ele alacağız:

• Grafiğin Temel Kavramlarına Kısa Bir Bakış
• Dijkstra Algoritmasının Kullanımını Anlayın
• Adım Adım Bir Örnekle Algoritmanın Çalışmasını Anlayın

Öyleyse başlayalım.

Grafiklere Kısa Bir Giriş

Grafikler öğeler arasındaki 'bağlantıları' temsil eden doğrusal olmayan veri yapılarıdır. Bu elementler olarak bilinir. Köşeler ve grafikteki herhangi iki köşeyi birleştiren çizgiler veya yaylar olarak bilinir. Kenarlar . Daha resmi olarak, bir Grafik şunları içerir: bir dizi Köşe (V) Ve bir dizi Kenar (E) . Grafik şu şekilde gösterilir: G(V, E) .

Grafiğin Bileşenleri

Köşeler:Köşeler, gerçek hayattaki nesneleri, kişileri veya varlıkları temsil etmek için kullanılan grafiğin temel birimleridir. Bazen köşeler aynı zamanda Düğümler olarak da bilinir.Kenarlar:Kenarlar çizilir veya grafiğin iki köşesini birleştirmek için kullanılır. Bazen kenarlar Yaylar olarak da bilinir.

Aşağıdaki şekilde bir Grafiğin grafiksel gösterimi gösterilmektedir:

Şekil 1: Bir Grafiğin Grafiksel Gösterimi

Yukarıdaki şekilde Köşeler/Düğümler Renkli Dairelerle, Kenarlar ise düğümleri birleştiren çizgilerle gösterilmiştir.

Grafiklerin Uygulamaları

Grafikler birçok gerçek hayat problemini çözmek için kullanılır. Ağları temsil etmek için grafikler kullanılır. Bu ağlar bir şehirdeki telefon veya devre ağlarını veya yolları içerebilir.

matematik rastgele java

Örneğin, köşelerin ürünleri gönderen veya alan tesisleri gösterdiği ve kenarların bunları birbirine bağlayan yolları veya yolları temsil ettiği bir ulaşım ağı modeli tasarlamak için Grafikleri kullanabiliriz. Aşağıdaki aynı şeyin resimli bir temsilidir:

Şekil 2: Ulaşım Ağının Resimli Gösterimi

Grafikler ayrıca LinkedIn, Facebook, Twitter ve daha fazlası gibi farklı Sosyal Medya Platformlarında da kullanılmaktadır. Örneğin Facebook gibi platformlar, her kişinin bir tepe noktasıyla gösterildiği ve her birinin Kişi Kimliği, Adı, Cinsiyeti, Adresi vb. bilgileri içeren bir yapı olduğu kullanıcılarının verilerini depolamak için Grafikler kullanır.

Grafik Türleri

Grafikler iki türe ayrılabilir:

1. Yönlendirilmemiş Grafik
2. Yönlendirilmiş grafik

Yönlendirilmemiş Grafik: Yönü olmayan kenarları olan bir Grafik, Yönsüz Grafik olarak adlandırılır. Bu grafiğin kenarları, her bir kenarın her iki yönde de geçilebildiği iki yönlü bir ilişkiyi ifade eder. Aşağıdaki şekilde dört düğüm ve beş kenar içeren basit, yönlendirilmemiş bir grafik gösterilmektedir.

Figür 3: Basit Yönlendirilmemiş Grafik

Yönlendirilmiş grafik: Yönlü kenarları olan bir Grafik, Yönlendirilmiş Grafik olarak adlandırılır. Bu grafiğin kenarları, her bir kenarın yalnızca tek bir yönde geçilebildiği tek yönlü bir ilişkiyi ifade eder. Aşağıdaki şekilde dört düğüm ve beş kenar içeren basit yönlendirilmiş bir grafik gösterilmektedir.

Şekil 4: Basit Yönlendirilmiş Grafik

Bir grafik gösteriminde kenarların mutlak uzunluğu, konumu veya yöneliminin karakteristik olarak bir anlamı yoktur. Başka bir deyişle, grafiğin temel yapısı değişmiyorsa, köşeleri yeniden düzenleyerek veya kenarları bozarak aynı grafiği farklı şekillerde görselleştirebiliriz.

Ağırlıklı Grafikler Nedir?

Her kenara bir 'ağırlık' atanırsa Grafiğe Ağırlıklı denir. Bir kenarın ağırlığı mesafeyi, zamanı veya bağladığı köşe çifti arasındaki 'bağlantıyı' modelleyen herhangi bir şeyi belirtebilir.

Örneğin aşağıdaki Ağırlıklandırılmış Grafik şeklinde her kenarın yanında mavi bir sayı görebiliyoruz. Bu sayı, karşılık gelen kenarın ağırlığını belirtmek için kullanılır.

Şekil 5: Ağırlıklandırılmış Grafik Örneği

Dijkstra Algoritmasına Giriş

Artık bazı temel Grafik kavramlarını bildiğimize göre Dijkstra Algoritması kavramını anlamaya geçelim.

Google Haritalar'ın iki yer arasındaki en kısa ve hızlı rotayı nasıl bulduğunu hiç merak ettiniz mi?

Cevap şu: Dijkstra'nın Algoritması . Dijkstra'nın Algoritması bir Grafik algoritmasıdır en kısa yolu bulan bir kaynak tepe noktasından Grafikteki tüm diğer köşelere (tek kaynak en kısa yol). Yalnızca pozitif ağırlıklara sahip Ağırlıklı Grafikler üzerinde çalışan bir Açgözlü Algoritma türüdür. Dijkstra Algoritmasının zaman karmaşıklığı Ç(V²) grafiğin bitişiklik matrisi gösterimi yardımıyla. Bu sefer karmaşıklık azaltılabilir O((V + E) log V) grafiğin bir bitişiklik listesi gösterimi yardımıyla, burada İÇİNDE köşe sayısıdır ve VE grafikteki kenarların sayısıdır.

Dijkstra Algoritmasının Tarihçesi

Dijkstra Algoritması tarafından tasarlandı ve yayınlandı Dr. Edsger W. Dijkstra Hollandalı Bilgisayar Bilimcisi, Yazılım Mühendisi, Programcı, Bilim Denemecisi ve Sistem Bilimcisi.

2001 yılında ACM dergisinin İletişimleri için Philip L. Frana ile yapılan röportajda Dr. Edsger W. Dijkstra şunu açıkladı:

'Genel olarak Rotterdam'dan Groningen'e seyahat etmenin en kısa yolu nedir: belirli bir şehirden belirli bir şehre? Yaklaşık yirmi dakikada tasarladığım en kısa yol algoritmasıdır. Bir sabah genç nişanlımla Amsterdam'da alışveriş yapıyorduk ve yorgun bir şekilde kafenin terasında oturup bir fincan kahve içtik ve bunu yapıp yapamayacağımı düşünüyordum ve ardından en kısa yolu algoritma olarak tasarladım. . Dediğim gibi yirmi dakikalık bir icattı. Aslında üç yıl sonra, '59'da yayımlandı. Yayın hala okunabilir durumda, aslında oldukça hoş. Bu kadar güzel olmasının sebeplerinden biri de kalem kağıtsız tasarlamamdı. Daha sonra kalem ve kağıt olmadan tasarım yapmanın avantajlarından birinin, neredeyse tüm önlenebilir karmaşıklıklardan kaçınmak zorunda kalmanız olduğunu öğrendim. Sonunda bu algoritma beni çok şaşırttı ve şöhretimin temel taşlarından biri haline geldi.'

Dijkstra, 1956 yılında Amsterdam'daki Matematik Merkezi'nde programcı olarak çalışırken, ARMAC olarak bilinen yeni bir bilgisayarın yeteneklerini göstermek için en kısa yol problemini düşündü. Amacı, hem bir sorunu hem de bilgisayar altyapısı olmayan kişilerin anlayabileceği (bilgisayar tarafından üretilen) bir çözümü seçmekti. En kısa yol algoritmasını geliştirdi ve daha sonra bunu Hollanda'daki 64 şehrin (64 şehir, yani şehir numarasını kodlamak için 6 bit yeterli olacaktır) belli belirsiz kısaltılmış bir ulaşım haritası için ARMAC için uyguladı. Bir yıl sonra, enstitünün bir sonraki bilgisayarını çalıştıran donanım mühendislerinin başka bir sorunuyla karşılaştı: Makinenin arka panelindeki pinleri bağlamak için gereken kablo miktarını en aza indirmek. Çözüm olarak Prim'in minimal yayılan ağaç algoritması adı verilen algoritmayı yeniden keşfetti ve 1959 yılında yayınladı.

Dijkstra Algoritmasının Temelleri

Dijkstra Algoritmasının temel kavramları şunlardır:

1. Dijkstra Algoritması seçtiğimiz düğümden (kaynak düğüm) başlar ve o düğüm ile grafikteki diğer tüm düğümler arasındaki en kısa yolu bulmak için grafiği inceler.
2. Algoritma, her düğümden kaynak düğüme kadar mevcut olarak kabul edilen en kısa mesafenin kayıtlarını tutar ve daha kısa bir yol bulduğunda bu değerleri günceller.
3. Algoritma, kaynak ile başka bir düğüm arasındaki en kısa yolu bulduğunda, bu düğüm 'ziyaret edildi' olarak işaretlenir ve yola dahil edilir.
4. Bu prosedür, grafikteki tüm düğümler yola dahil edilene kadar devam eder. Bu şekilde, kaynak düğümü diğer tüm düğümlere bağlayan ve her düğüme ulaşmak için mümkün olan en kısa yolu takip eden bir yola sahip oluruz.

Dijkstra Algoritmasının Çalışmasını Anlamak

A grafik Ve kaynak tepe noktası Dijkstra Algoritmasının gereksinimleridir. Bu Algoritma Açgözlü Yaklaşım üzerine kuruludur ve böylece Algoritmanın her adımında yerel olarak en uygun seçimi (bu durumda yerel minimum) bulur.

Bu Algoritmadaki her Köşe kendisi için tanımlanmış iki özelliğe sahip olacaktır:

1. Ziyaret Edilen Mülk
2. Yol Özelliği

Bu özellikleri kısaca anlayalım.

Ziyaret Edilen Mülk:

1. 'Ziyaret edilen' özelliği, düğümün ziyaret edilip edilmediğini belirtir.
2. Bu özelliği herhangi bir düğümü tekrar ziyaret etmemek için kullanıyoruz.
3. Bir düğüm yalnızca en kısa yol bulunduğunda ziyaret edilmiş olarak işaretlenir.

Yol Özelliği:

1. 'Path' özelliği, düğüme giden geçerli minimum yolun değerini saklar.
2. Mevcut minimum yol şu ana kadar bu düğüme ulaştığımız en kısa yolu ifade eder.
3. Bu özellik, düğümün herhangi bir komşusu ziyaret edildiğinde revize edilir.
4. Bu özellik önemlidir çünkü her düğüm için son cevabı saklayacaktır.

Başlangıçta, henüz ziyaret edilmedikleri için ziyaret edilmemiş tüm köşeleri veya düğümleri işaretliyoruz. Kaynak düğüm dışında tüm düğümlere giden yol da sonsuz olarak ayarlanmıştır. Ayrıca kaynak düğüme giden yol sıfıra (0) ayarlanmıştır.

Daha sonra kaynak düğümü seçip ziyaret edildi olarak işaretliyoruz. Bundan sonra kaynak düğümün tüm komşu düğümlerine erişiyoruz ve her düğümde gevşeme gerçekleştiriyoruz. Gevşeme, bir düğüme ulaşmanın maliyetinin başka bir düğüm yardımıyla düşürülmesi işlemidir.

Gevşetme sürecinde, her düğümün yolu, düğümün mevcut yolu, önceki düğüme giden yolun toplamı ve önceki düğümden mevcut düğüme giden yol arasından minimum değere revize edilir.

p[n]'in n düğümü için mevcut yolun değeri olduğunu, p[m]'nin daha önce ziyaret edilen m düğümüne kadar olan yolun değeri olduğunu ve w'nin mevcut düğüm ile mevcut düğüm arasındaki kenarın ağırlığı olduğunu varsayalım. daha önce ziyaret edilen bir tanesi (kenar ağırlığı n ile m arasında).

Matematiksel anlamda gevşeme şu şekilde örneklenebilir:

p[n] = minimum(p[n], p[m] + w)

Daha sonra ziyaret edilmemiş bir düğümü, sonraki her adımda ziyaret edilen en az yola sahip olarak işaretler ve komşusunun yollarını güncelleriz.

Grafikteki tüm düğümler ziyaret edildi olarak işaretlenene kadar bu prosedürü tekrarlıyoruz.

Ziyaret edilen kümeye bir düğüm eklediğimizde, tüm komşu düğümlerin yolu da buna göre değişir.

Herhangi bir düğüme ulaşılamaz durumda bırakılırsa (bağlantısı kesilmiş bileşen), yolu 'sonsuz' olarak kalır. Kaynağın ayrı bir bileşen olması durumunda, diğer tüm düğümlere giden yol 'sonsuz' kalır.

Bir Örnekle Dijkstra Algoritmasını Anlamak

Dijkstra Algoritmasını uygulamak için izleyeceğimiz adım aşağıdadır:

Aşama 1: Öncelikle kaynak düğümü mevcut uzaklığı 0 olacak şekilde işaretleyip geri kalan düğümleri INFINITY olarak ayarlayacağız.

Adım 2: Daha sonra ziyaret edilmemiş düğümü en küçük akım mesafesine sahip olarak geçerli düğüm olarak ayarlayacağız, diyelim ki X.

Aşama 3: Mevcut X düğümünün her bir komşusu N için: Daha sonra X'in mevcut mesafesini X-N'yi birleştiren kenarın ağırlığıyla toplayacağız. N'nin mevcut mesafesinden küçükse, bunu N'nin yeni mevcut mesafesi olarak ayarlayın.

dizeye Java boolean

Adım 4: Daha sonra mevcut X düğümünü ziyaret edildi olarak işaretleyeceğiz.

Adım 5: İşlemi şu andan itibaren tekrarlayacağız: 'Adım 2' grafikte ziyaret edilmemiş herhangi bir düğüm kaldıysa.

Şimdi bir örnek yardımıyla algoritmanın uygulamasını anlayalım:

Şekil 6: Verilen Grafik

1. Yukarıdaki grafiği girdi olarak kullanacağız, düğüm ile A kaynak olarak.
2. Öncelikle tüm düğümleri ziyaret edilmemiş olarak işaretleyeceğiz.
3. Yolu biz belirleyeceğiz 0 düğümde A Ve SONSUZLUK diğer tüm düğümler için.
4. Şimdi kaynak düğümü işaretleyeceğiz A Ziyaret edildiği gibi ve komşu düğümlerine erişin.
   Not: Yalnızca komşu düğümlere eriştik, onları ziyaret etmedik.
5. Şimdi düğümün yolunu güncelleyeceğiz B ile 4 Gevşeme yardımıyla çünkü düğüme giden yol A dır-dir 0 ve düğümden gelen yol A ile B dır-dir 4 , ve minimum((0 + 4), SONSUZ) dır-dir 4 .
6. Ayrıca düğümün yolunu da güncelleyeceğiz C ile 5 Gevşeme yardımıyla çünkü düğüme giden yol A dır-dir 0 ve düğümden gelen yol A ile C dır-dir 5 , ve minimum((0 + 5), SONSUZ) dır-dir 5 . Düğümün her iki komşusu A artık rahatız; bu nedenle ilerleyebiliriz.
7. Şimdi en az yola sahip bir sonraki ziyaret edilmemiş düğümü seçip ziyaret edeceğiz. Bu nedenle düğümü ziyaret edeceğiz B ve ziyaret edilmeyen komşularına rahatlama uygulayın. Gevşeme işlemini gerçekleştirdikten sonra düğüme giden yol C kalacak 5 , oysa düğüme giden yol VE Olacak on bir ve düğüme giden yol D Olacak 13 .
8. Şimdi düğümü ziyaret edeceğiz VE ve komşu düğümlerinde gevşeme gerçekleştirin B, D , Ve F . Yalnızca düğüm olduğundan F ziyaret edilmezse rahatlayacaktır. Böylece düğüme giden yol B olduğu gibi kalacak, yani 4 , düğüme giden yol D ayrıca kalacak 13 ve düğüme giden yol F Olacak 14 (8 + 6) .
9. Şimdi düğümü ziyaret edeceğiz D ve yalnızca düğüm F rahatlamış olacak. Ancak düğüme giden yol F değişmeden kalacaktır, yani, 14 .
10. Yalnızca düğüm olduğundan F Kalan tüm düğümler zaten ziyaret edildiğinden onu ziyaret edeceğiz ancak herhangi bir rahatlama yapmayacağız.
11. Grafiğin tüm düğümleri ziyaret edildiğinde program sona erecektir.

Dolayısıyla ulaştığımız son yollar şunlardır:

 A = 0 B = 4 (A -> B) C = 5 (A -> C) D = 4 + 9 = 13 (A -> B -> D) E = 5 + 3 = 8 (A -> C -> E) F = 5 + 3 + 6 = 14 (A -> C -> E -> F) 

Dijkstra Algoritmasının Sahte Kodu

Şimdi Dijkstra Algoritmasının sözde kodunu anlayacağız.

• Her düğümün yol mesafesinin kaydını tutmalıyız. Bu nedenle, her düğümün yol mesafesini n boyutunda bir dizide saklayabiliriz; burada n, toplam düğüm sayısıdır.
• Üstelik en kısa yolu, o yolun uzunluğuyla birlikte almak istiyoruz. Bu sorunun üstesinden gelmek için her düğümü, yol uzunluğunu en son güncelleyen düğümle eşleştireceğiz.
• Algoritma tamamlandıktan sonra, yolu almak için hedef düğümü kaynak düğüme kadar geriye doğru izleyebiliriz.
• En az yol mesafesine sahip düğümü verimli bir şekilde almak için minimum Öncelik Kuyruğu'nu kullanabiliriz.

Şimdi yukarıdaki çizimin sözde kodunu uygulayalım:

Sahte kod:

 function Dijkstra_Algorithm(Graph, source_node) // iterating through the nodes in Graph and set their distances to INFINITY for each node N in Graph: distance[N] = INFINITY previous[N] = NULL If N != source_node, add N to Priority Queue G // setting the distance of the source node of the Graph to 0 distance[source_node] = 0 // iterating until the Priority Queue G is not empty while G is NOT empty: // selecting a node Q having the least distance and marking it as visited Q = node in G with the least distance[] mark Q visited // iterating through the unvisited neighboring nodes of the node Q and performing relaxation accordingly for each unvisited neighbor node N of Q: temporary_distance = distance[Q] + distance_between(Q, N) // if the temporary distance is less than the given distance of the path to the Node, updating the resultant distance with the minimum value if temporary_distance <distance[n] distance[n] :="temporary_distance" previous[n] returning the final list of distance return distance[], previous[] < pre> <p> <strong>Explanation:</strong> </p> <p>In the above pseudocode, we have defined a function that accepts multiple parameters - the Graph consisting of the nodes and the source node. Inside this function, we have iterated through each node in the Graph, set their initial distance to <strong>INFINITY</strong> , and set the previous node value to <strong>NULL</strong> . We have also checked whether any selected node is not a source node and added the same into the Priority Queue. Moreover, we have set the distance of the source node to <strong>0</strong> . We then iterated through the nodes in the priority queue, selected the node with the least distance, and marked it as visited. We then iterated through the unvisited neighboring nodes of the selected node and performed relaxation accordingly. At last, we have compared both the distances (original and temporary distance) between the source node and the destination node, updated the resultant distance with the minimum value and previous node information, and returned the final list of distances with their previous node information.</p> <h2>Implementation of Dijkstra&apos;s Algorithm in Different Programming Languages</h2> <p>Now that we have successfully understood the pseudocode of Dijkstra&apos;s Algorithm, it is time to see its implementation in different programming languages like C, C++, Java, and Python.</p> <h3>Code for Dijkstra&apos;s Algorithm in C</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the C Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.c</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in C // importing the standard I/O header file #include // defining some constants #define INF 9999 #define MAX 10 // prototyping of the function void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start); // defining the function for Dijkstra&apos;s Algorithm void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start) { int cost[MAX][MAX], distance[MAX], previous[MAX]; int visited_nodes[MAX], counter, minimum_distance, next_node, i, j; // creating cost matrix for (i = 0; i <size; i++) for (j="0;" j < size; j++) if (graph[i][j]="=" 0) cost[i][j]="INF;" else (i="0;" i { distance[i]="cost[start][i];" previous[i]="start;" visited_nodes[i]="0;" } distance[start]="0;" visited_nodes[start]="1;" counter="1;" while (counter size - 1) minimum_distance="INF;" (distance[i] && !visited_nodes[i]) next_node="i;" visited_nodes[next_node]="1;" (!visited_nodes[i]) (minimum_distance + cost[next_node][i] distance[i]) cost[next_node][i]; counter++; printing the distance !="start)" printf('
distance from source node to %d: %d', i, distance[i]); main function int main() defining variables graph[max][max], j, size, source; declaring of matrix nodes graph graph[0][0]="0;" graph[0][1]="4;" graph[0][2]="0;" graph[0][3]="0;" graph[0][4]="0;" graph[0][5]="8;" graph[0][6]="0;" graph[1][0]="4;" graph[1][1]="0;" graph[1][2]="8;" graph[1][3]="0;" graph[1][4]="0;" graph[1][5]="11;" graph[1][6]="0;" graph[2][0]="0;" graph[2][1]="8;" graph[2][2]="0;" graph[2][3]="7;" graph[2][4]="0;" graph[2][5]="4;" graph[2][6]="0;" graph[3][0]="0;" graph[3][1]="0;" graph[3][2]="7;" graph[3][3]="0;" graph[3][4]="9;" graph[3][5]="14;" graph[3][6]="0;" graph[4][0]="0;" graph[4][1]="0;" graph[4][2]="0;" graph[4][3]="9;" graph[4][4]="0;" graph[4][5]="10;" graph[4][6]="2;" graph[5][0]="0;" graph[5][1]="0;" graph[5][2]="4;" graph[5][3]="14;" graph[5][4]="10;" graph[5][5]="0;" graph[5][6]="2;" graph[6][0]="0;" graph[6][1]="0;" graph[6][2]="0;" graph[6][3]="0;" graph[6][4]="2;" graph[6][5]="0;" graph[6][6]="1;" calling dijkstraalgorithm() by passing graph, number and dijkstraalgorithm(graph, source); return 0; pre> <p> <strong>Output</strong> </p> <pre> Distance from the Source Node to 1: 4 Distance from the Source Node to 2: 12 Distance from the Source Node to 3: 19 Distance from the Source Node to 4: 12 Distance from the Source Node to 5: 8 Distance from the Source Node to 6: 10 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have included the <strong>stdio.h</strong> header file defined two constant values: <strong>INF = 9999</strong> and <strong>MAX = 10</strong> . We have declared the prototyping of the function and then defined the function for Dijkstra&apos;s Algorithm as <strong>DijkstraAlgorithm</strong> that accepts three arguments - the Graph consisting of the nodes, the number of nodes in the Graph, and the source node. Inside this function, we have defined some data structures such as a 2D matrix that will work as the Priority Queue for the algorithm, an array to main the distance between the nodes, an array to maintain the record of previous nodes, an array to store the visited nodes information, and some integer variables to store minimum distance value, counter, next node value and more. We then used a <strong>nested for-loop</strong> to iterate through the nodes of the Graph and add them to the priority queue accordingly. We have again used the <strong>for-loop</strong> to iterate through the elements in the priority queue starting from the source node and update their distances. Outside the loop, we have set the distance of the source node as <strong>0</strong> and marked it as visited in the <strong>visited_nodes[]</strong> array. We then set the counter value as one and used the <strong>while</strong> loop iterating through the number of nodes. Inside this loop, we have set the value of <strong>minimum_distance</strong> as <strong>INF</strong> and used the <strong>for-loop</strong> to update the value of the <strong>minimum_distance</strong> variable with the minimum value from a <strong>distance[]</strong> array. We then iterated through the unvisited neighboring nodes of the selected node using the <strong>for-loop</strong> and performed relaxation. We then printed the resulting data of the distances calculated using Dijkstra&apos;s Algorithm.</p> <p>In the <strong>main</strong> function, we have defined and declared the variables representing the Graph, the number of nodes, and the source node. At last, we have called the <strong>DijkstraAlgorithm()</strong> function by passing the required parameters.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in C++</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the C++ Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.cpp</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in C++ // importing the required header files #include #include // defining constant #define MAX_INT 10000000 // using the standard namespace using namespace std; // prototyping of the DijkstraAlgorithm() function void DijkstraAlgorithm(); // main function int main() { DijkstraAlgorithm(); return 0; } // declaring the classes class Vertex; class Edge; // prototyping the functions void Dijkstra(); vector* Adjacent_Remaining_Nodes(Vertex* vertex); Vertex* Extract_Smallest(vector&amp; vertices); int Distance(Vertex* vertexOne, Vertex* vertexTwo); bool Contains(vector&amp; vertices, Vertex* vertex); void Print_Shortest_Route_To(Vertex* des); // instantiating the classes vector vertices; vector edges; // defining the class for the vertices of the graph class Vertex { public: Vertex(char id) : id(id), prev(NULL), distance_from_start(MAX_INT) { vertices.push_back(this); } public: char id; Vertex* prev; int distance_from_start; }; // defining the class for the edges of the graph class Edge { public: Edge(Vertex* vertexOne, Vertex* vertexTwo, int distance) : vertexOne(vertexOne), vertexTwo(vertexTwo), distance(distance) { edges.push_back(this); } bool Connects(Vertex* vertexOne, Vertex* vertexTwo) public: Vertex* vertexOne; Vertex* vertexTwo; int distance; }; // defining the function to collect the details of the graph void DijkstraAlgorithm() { // declaring some vertices Vertex* vertex_a = new Vertex(&apos;A&apos;); Vertex* vertex_b = new Vertex(&apos;B&apos;); Vertex* vertex_c = new Vertex(&apos;C&apos;); Vertex* vertex_d = new Vertex(&apos;D&apos;); Vertex* vertex_e = new Vertex(&apos;E&apos;); Vertex* vertex_f = new Vertex(&apos;F&apos;); Vertex* vertex_g = new Vertex(&apos;G&apos;); // declaring some edges Edge* edge_1 = new Edge(vertex_a, vertex_c, 1); Edge* edge_2 = new Edge(vertex_a, vertex_d, 2); Edge* edge_3 = new Edge(vertex_b, vertex_c, 2); Edge* edge_4 = new Edge(vertex_c, vertex_d, 1); Edge* edge_5 = new Edge(vertex_b, vertex_f, 3); Edge* edge_6 = new Edge(vertex_c, vertex_e, 3); Edge* edge_7 = new Edge(vertex_e, vertex_f, 2); Edge* edge_8 = new Edge(vertex_d, vertex_g, 1); Edge* edge_9 = new Edge(vertex_g, vertex_f, 1); vertex_a -&gt; distance_from_start = 0; // setting a start vertex // calling the Dijkstra() function to find the shortest route possible Dijkstra(); // calling the Print_Shortest_Route_To() function to print the shortest route from the source vertex to the destination vertex Print_Shortest_Route_To(vertex_f); } // defining the function for Dijkstra&apos;s Algorithm void Dijkstra() { while (vertices.size() &gt; 0) { Vertex* smallest = Extract_Smallest(vertices); vector* adjacent_nodes = Adjacent_Remaining_Nodes(smallest); const int size = adjacent_nodes -&gt; size(); for (int i = 0; i at(i); int distance = Distance(smallest, adjacent) + smallest -&gt; distance_from_start; if (distance distance_from_start) { adjacent -&gt; distance_from_start = distance; adjacent -&gt; prev = smallest; } } delete adjacent_nodes; } } // defining the function to find the vertex with the shortest distance, removing it, and returning it Vertex* Extract_Smallest(vector&amp; vertices) { int size = vertices.size(); if (size == 0) return NULL; int smallest_position = 0; Vertex* smallest = vertices.at(0); for (int i = 1; i distance_from_start distance_from_start) { smallest = current; smallest_position = i; } } vertices.erase(vertices.begin() + smallest_position); return smallest; } // defining the function to return all vertices adjacent to &apos;vertex&apos; which are still in the &apos;vertices&apos; collection. vector* Adjacent_Remaining_Nodes(Vertex* vertex) { vector* adjacent_nodes = new vector(); const int size = edges.size(); for (int i = 0; i vertexOne == vertex) { adjacent = edge -&gt; vertexTwo; } else if (edge -&gt; vertexTwo == vertex) { adjacent = edge -&gt; vertexOne; } if (adjacent &amp;&amp; Contains(vertices, adjacent)) { adjacent_nodes -&gt; push_back(adjacent); } } return adjacent_nodes; } // defining the function to return distance between two connected vertices int Distance(Vertex* vertexOne, Vertex* vertexTwo) { const int size = edges.size(); for (int i = 0; i Connects(vertexOne, vertexTwo)) { return edge -&gt; distance; } } return -1; // should never happen } // defining the function to check if the &apos;vertices&apos; vector contains &apos;vertex&apos; bool Contains(vector&amp; vertices, Vertex* vertex) { const int size = vertices.size(); for (int i = 0; i <size; ++i) { if (vertex="=" vertices.at(i)) return true; } false; defining the function to print shortest route destination void print_shortest_route_to(vertex* des) vertex* prev="des;" cout << 'distance from start: ' < distance_from_start endl; while (prev) id prev; pre> <p> <strong>Output</strong> </p> <pre> Distance from start: 4 F G D A </pre> <p> <strong>Explanation:</strong> </p> <p>In the above code snippet, we included the <strong>&apos;iostream&apos;</strong> and <strong>&apos;vector&apos;</strong> header files and defined a constant value as <strong>MAX_INT = 10000000</strong> . We then used the standard namespace and prototyped the <strong>DijkstraAlgorithm()</strong> function. We then defined the main function of the program within, which we have called the <strong>DijkstraAlgorithm()</strong> function. After that, we declared some classes to create vertices and edges. We have also prototyped more functions to find the shortest possible path from the source vertex to the destination vertex and instantiated the Vertex and Edge classes. We then defined both classes to create the vertices and edges of the graph. We have then defined the <strong>DijkstraAlgorithm()</strong> function to create a graph and perform different operations. Inside this function, we have declared some vertices and edges. We then set the source vertex of the graph and called the <strong>Dijkstra()</strong> function to find the shortest possible distance and <strong>Print_Shortest_Route_To()</strong> function to print the shortest distance from the source vertex to vertex <strong>&apos;F&apos;</strong> . We have then defined the <strong>Dijkstra()</strong> function to calculate the shortest possible distances of the all the vertices from the source vertex. We have also defined some more functions to find the vertex with the shortest distance to return all the vertices adjacent to the remaining vertex, to return the distance between two connected vertices, to check if the selected vertex exists in the graph, and to print the shortest possible path from the source vertex to the destination vertex.</p> <p>As a result, the required shortest path for the vertex <strong>&apos;F&apos;</strong> from the source node is printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Java</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Java Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.java</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format('distance from %s to %s', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;></pre></size;></pre></size;></pre></distance[n]>

Açıklama:

Yukarıdaki kod parçacığına şunları ekledik: stdio.h başlık dosyası iki sabit değer tanımladı: INF = 9999 Ve MAKS = 10 . Fonksiyonun prototipini ilan ettik ve ardından Dijkstra Algoritması için fonksiyonu şu şekilde tanımladık: Dijkstra Algoritması üç argümanı kabul eder: düğümlerden oluşan Grafik, Grafikteki düğüm sayısı ve kaynak düğüm. Bu fonksiyonun içerisinde algoritma için Öncelik Kuyruğu görevi görecek 2 boyutlu matris, düğümler arasındaki mesafeyi koruyacak bir dizi, önceki düğümlerin kaydını tutacak bir dizi, saklayacak bir dizi gibi bazı veri yapılarını tanımladık. ziyaret edilen düğüm bilgileri ve minimum mesafe değerini, sayacı, sonraki düğüm değerini ve daha fazlasını saklamak için bazı tamsayı değişkenleri. Daha sonra bir iç içe döngü Grafiğin düğümleri arasında yineleme yapmak ve bunları buna göre öncelik sırasına eklemek. Yine kullandık döngü için kaynak düğümden başlayarak öncelik kuyruğundaki öğeler arasında yineleme yapmak ve mesafelerini güncellemek. Döngünün dışında kaynak düğümün mesafesini şu şekilde ayarladık: 0 ve bunu şurada ziyaret edildi olarak işaretledim ziyaret edilen_düğümler[] sıralamak. Daha sonra sayaç değerini bir olarak ayarladık ve sırasında düğüm sayısı boyunca yinelenen döngü. Bu döngünün içinde değerini ayarladık. minimum_distance gibi INF ve kullandı döngü için değerini güncellemek için minimum_distance minimum değere sahip değişken mesafe[] sıralamak. Daha sonra seçilen düğümün ziyaret edilmemiş komşu düğümleri arasında yineleme yaptık. döngü için ve rahatlama gerçekleştirdi. Daha sonra Dijkstra Algoritması kullanılarak hesaplanan mesafelerin sonuç verilerini yazdırdık.

İçinde ana fonksiyonunda Grafiği temsil eden değişkenleri, düğüm sayısını ve kaynak düğümü tanımladık ve bildirdik. Sonunda aradık DijkstraAlgoritması() Gerekli parametreleri ileterek işlev.

Sonuç olarak kaynak düğümden itibaren her düğüm için gerekli olan mümkün olan en kısa yollar kullanıcılara yazdırılır.

Dijkstra Algoritmasının C++ dilindeki kodu

Aşağıda Dijkstra Algoritmasının C++ Programlama Dilinde uygulanması yer almaktadır:

Dosya: DijkstraAlgorithm.cpp

 // Implementation of Dijkstra&apos;s Algorithm in C++ // importing the required header files #include #include // defining constant #define MAX_INT 10000000 // using the standard namespace using namespace std; // prototyping of the DijkstraAlgorithm() function void DijkstraAlgorithm(); // main function int main() { DijkstraAlgorithm(); return 0; } // declaring the classes class Vertex; class Edge; // prototyping the functions void Dijkstra(); vector* Adjacent_Remaining_Nodes(Vertex* vertex); Vertex* Extract_Smallest(vector&amp; vertices); int Distance(Vertex* vertexOne, Vertex* vertexTwo); bool Contains(vector&amp; vertices, Vertex* vertex); void Print_Shortest_Route_To(Vertex* des); // instantiating the classes vector vertices; vector edges; // defining the class for the vertices of the graph class Vertex { public: Vertex(char id) : id(id), prev(NULL), distance_from_start(MAX_INT) { vertices.push_back(this); } public: char id; Vertex* prev; int distance_from_start; }; // defining the class for the edges of the graph class Edge { public: Edge(Vertex* vertexOne, Vertex* vertexTwo, int distance) : vertexOne(vertexOne), vertexTwo(vertexTwo), distance(distance) { edges.push_back(this); } bool Connects(Vertex* vertexOne, Vertex* vertexTwo) public: Vertex* vertexOne; Vertex* vertexTwo; int distance; }; // defining the function to collect the details of the graph void DijkstraAlgorithm() { // declaring some vertices Vertex* vertex_a = new Vertex(&apos;A&apos;); Vertex* vertex_b = new Vertex(&apos;B&apos;); Vertex* vertex_c = new Vertex(&apos;C&apos;); Vertex* vertex_d = new Vertex(&apos;D&apos;); Vertex* vertex_e = new Vertex(&apos;E&apos;); Vertex* vertex_f = new Vertex(&apos;F&apos;); Vertex* vertex_g = new Vertex(&apos;G&apos;); // declaring some edges Edge* edge_1 = new Edge(vertex_a, vertex_c, 1); Edge* edge_2 = new Edge(vertex_a, vertex_d, 2); Edge* edge_3 = new Edge(vertex_b, vertex_c, 2); Edge* edge_4 = new Edge(vertex_c, vertex_d, 1); Edge* edge_5 = new Edge(vertex_b, vertex_f, 3); Edge* edge_6 = new Edge(vertex_c, vertex_e, 3); Edge* edge_7 = new Edge(vertex_e, vertex_f, 2); Edge* edge_8 = new Edge(vertex_d, vertex_g, 1); Edge* edge_9 = new Edge(vertex_g, vertex_f, 1); vertex_a -&gt; distance_from_start = 0; // setting a start vertex // calling the Dijkstra() function to find the shortest route possible Dijkstra(); // calling the Print_Shortest_Route_To() function to print the shortest route from the source vertex to the destination vertex Print_Shortest_Route_To(vertex_f); } // defining the function for Dijkstra&apos;s Algorithm void Dijkstra() { while (vertices.size() &gt; 0) { Vertex* smallest = Extract_Smallest(vertices); vector* adjacent_nodes = Adjacent_Remaining_Nodes(smallest); const int size = adjacent_nodes -&gt; size(); for (int i = 0; i at(i); int distance = Distance(smallest, adjacent) + smallest -&gt; distance_from_start; if (distance distance_from_start) { adjacent -&gt; distance_from_start = distance; adjacent -&gt; prev = smallest; } } delete adjacent_nodes; } } // defining the function to find the vertex with the shortest distance, removing it, and returning it Vertex* Extract_Smallest(vector&amp; vertices) { int size = vertices.size(); if (size == 0) return NULL; int smallest_position = 0; Vertex* smallest = vertices.at(0); for (int i = 1; i distance_from_start distance_from_start) { smallest = current; smallest_position = i; } } vertices.erase(vertices.begin() + smallest_position); return smallest; } // defining the function to return all vertices adjacent to &apos;vertex&apos; which are still in the &apos;vertices&apos; collection. vector* Adjacent_Remaining_Nodes(Vertex* vertex) { vector* adjacent_nodes = new vector(); const int size = edges.size(); for (int i = 0; i vertexOne == vertex) { adjacent = edge -&gt; vertexTwo; } else if (edge -&gt; vertexTwo == vertex) { adjacent = edge -&gt; vertexOne; } if (adjacent &amp;&amp; Contains(vertices, adjacent)) { adjacent_nodes -&gt; push_back(adjacent); } } return adjacent_nodes; } // defining the function to return distance between two connected vertices int Distance(Vertex* vertexOne, Vertex* vertexTwo) { const int size = edges.size(); for (int i = 0; i Connects(vertexOne, vertexTwo)) { return edge -&gt; distance; } } return -1; // should never happen } // defining the function to check if the &apos;vertices&apos; vector contains &apos;vertex&apos; bool Contains(vector&amp; vertices, Vertex* vertex) { const int size = vertices.size(); for (int i = 0; i <size; ++i) { if (vertex="=" vertices.at(i)) return true; } false; defining the function to print shortest route destination void print_shortest_route_to(vertex* des) vertex* prev="des;" cout << \'distance from start: \' < distance_from_start endl; while (prev) id prev; pre> <p> <strong>Output</strong> </p> <pre> Distance from start: 4 F G D A </pre> <p> <strong>Explanation:</strong> </p> <p>In the above code snippet, we included the <strong>&apos;iostream&apos;</strong> and <strong>&apos;vector&apos;</strong> header files and defined a constant value as <strong>MAX_INT = 10000000</strong> . We then used the standard namespace and prototyped the <strong>DijkstraAlgorithm()</strong> function. We then defined the main function of the program within, which we have called the <strong>DijkstraAlgorithm()</strong> function. After that, we declared some classes to create vertices and edges. We have also prototyped more functions to find the shortest possible path from the source vertex to the destination vertex and instantiated the Vertex and Edge classes. We then defined both classes to create the vertices and edges of the graph. We have then defined the <strong>DijkstraAlgorithm()</strong> function to create a graph and perform different operations. Inside this function, we have declared some vertices and edges. We then set the source vertex of the graph and called the <strong>Dijkstra()</strong> function to find the shortest possible distance and <strong>Print_Shortest_Route_To()</strong> function to print the shortest distance from the source vertex to vertex <strong>&apos;F&apos;</strong> . We have then defined the <strong>Dijkstra()</strong> function to calculate the shortest possible distances of the all the vertices from the source vertex. We have also defined some more functions to find the vertex with the shortest distance to return all the vertices adjacent to the remaining vertex, to return the distance between two connected vertices, to check if the selected vertex exists in the graph, and to print the shortest possible path from the source vertex to the destination vertex.</p> <p>As a result, the required shortest path for the vertex <strong>&apos;F&apos;</strong> from the source node is printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Java</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Java Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.java</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format(\'distance from %s to %s\', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;></pre></size;>

Açıklama:

Yukarıdaki kod parçacığına şunları ekledik: 'io akışı' Ve 'vektör' başlık dosyaları ve olarak sabit bir değer tanımladım MAX_INT = 10000000 . Daha sonra standart ad alanını kullandık ve prototipini oluşturduk. DijkstraAlgoritması() işlev. Daha sonra programın içindeki ana işlevi tanımladık; buna DijkstraAlgoritması() işlev. Daha sonra köşe ve kenar oluşturmak için bazı sınıflar tanımladık. Ayrıca kaynak köşeden hedef köşeye mümkün olan en kısa yolu bulmak için daha fazla fonksiyonun prototipini yaptık ve Vertex ve Edge sınıflarını başlattık. Daha sonra grafiğin köşelerini ve kenarlarını oluşturmak için her iki sınıfı da tanımladık. Daha sonra tanımladık DijkstraAlgoritması() Bir grafik oluşturma ve farklı işlemler gerçekleştirme işlevi. Bu fonksiyonun içinde bazı köşe ve kenarları tanımladık. Daha sonra grafiğin kaynak tepe noktasını ayarladık ve Dijkstra() mümkün olan en kısa mesafeyi bulma işlevi ve Print_Shortest_Route_To() Kaynak tepe noktasından tepe noktasına en kısa mesafeyi yazdırma işlevi 'F' . Daha sonra tanımladık Dijkstra() Tüm köşelerin kaynak tepe noktasından mümkün olan en kısa mesafelerini hesaplama işlevi. Ayrıca en kısa mesafeye sahip köşeyi bulmak, kalan köşeye bitişik tüm köşeleri döndürmek, bağlantılı iki köşe arasındaki mesafeyi döndürmek, seçilen köşenin grafikte var olup olmadığını kontrol etmek ve grafiği yazdırmak için birkaç fonksiyon daha tanımladık. Kaynak köşeden hedef köşeye mümkün olan en kısa yol.

Sonuç olarak köşe için gereken en kısa yol 'F' Kullanıcılar için kaynak düğümden yazdırılır.

Java'da Dijkstra Algoritmasının Kodu

Aşağıda Dijkstra Algoritmasının Java Programlama Dilinde uygulanması yer almaktadır:

Dosya: DijkstraAlgorithm.java

 // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format(\'distance from %s to %s\', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;>

Açıklama:

Yukarıdaki kod parçacığında, genel bir sınıfı şu şekilde tanımladık: DijkstraAlgoritması() . Bu sınıfın içinde, genel bir yöntemi şu şekilde tanımladık: dijkstraAlgoritma() Kaynak köşeden hedef köşeye en kısa mesafeyi bulmak için. Bu yöntemin içinde düğüm sayısını saklayacak bir değişken tanımladık. Daha sonra ziyaret edilen köşelere ilişkin bilgileri depolamak için bir Boole dizisi ve ilgili mesafeleri depolamak için bir tamsayı dizisi tanımladık. Başlangıçta, her iki dizideki değerleri şu şekilde bildirdik: YANLIŞ Ve MAKSİMUM DEĞER , sırasıyla. Ayrıca kaynak tepe noktasının mesafesini sıfır olarak ayarladık ve döngü için Kaynak köşe ile hedef köşeler arasındaki mesafeyi minimum mesafeyle güncellemek için. Daha sonra seçilen köşenin komşu köşelerinin mesafelerini gevşeme yaparak güncelledik ve her köşe için en kısa mesafeleri yazdırdık. Daha sonra kaynak köşeden hedef köşeye olan minimum mesafeyi bulmak için bir yöntem tanımladık. Daha sonra grafiğin köşelerini bildirdiğimiz ve örneklendirdiğimiz ana işlevi tanımladık. DijkstraAlgoritması() sınıf. Sonunda aradık dijkstraAlgoritma() Kaynak köşe ile hedef köşeler arasındaki en kısa mesafeyi bulma yöntemi.

Sonuç olarak kaynak düğümden itibaren her düğüm için gerekli olan mümkün olan en kısa yollar kullanıcılara yazdırılır.

Python'da Dijkstra Algoritmasının Kodu

Aşağıda Dijkstra Algoritmasının Python Programlama Dilinde uygulanması yer almaktadır:

Dosya: DikstraAlgorithm.py

 # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0>

Çıktı

 Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 

Açıklama:

int java'ya bir dize yayınla

Yukarıdaki kod parçacığında, içe aktardık sistem modül ve düğümler ve kenarlar için değerlerden oluşan listeleri bildirdi. Daha sonra şu şekilde bir fonksiyon tanımladık: Ziyaret Edilecek() bir sonraki adımda hangi düğümün ziyaret edileceğini bulmak için. Daha sonra grafikteki toplam düğüm sayısını bulduk ve her düğüm için başlangıç ​​mesafelerini belirledik. Daha sonra kaynak düğümden hedef düğüme olan minimum mesafeyi hesapladık, komşu düğümlerde gevşeme gerçekleştirdik ve listedeki mesafeleri güncelledik. Daha sonra bu mesafeleri kullanıcılar için listeden yazdırdık.

Sonuç olarak kaynak düğümden itibaren her düğüm için gerekli olan mümkün olan en kısa yollar kullanıcılara yazdırılır.

Dijkstra Algoritmasının Zaman ve Uzay Karmaşıklığı

• Dijkstra Algoritmasının Zaman Karmaşıklığı O(E log V) Burada E kenar sayısı ve V köşe sayısıdır.
• Dijkstra Algoritmasının Uzay Karmaşıklığı O(V)'dir; burada V, köşelerin sayısıdır.

Dijkstra Algoritmasının Avantajları ve Dezavantajları

Dijkstra Algoritmasının bazı avantajlarını tartışalım:

1. Dijkstra Algoritmasını kullanmanın başlıca avantajlarından biri, neredeyse doğrusal bir zaman ve uzay karmaşıklığına sahip olmasıdır.
2. Bu algoritmayı, hedef tepe noktası için en kısa mesafeyi elde ettiğimizde algoritmayı durdurarak, tek bir tepe noktasından diğer tüm köşelere ve tek bir kaynak tepe noktasından tek bir hedef tepe noktasına giden en kısa yolu hesaplamak için kullanabiliriz.
3. Bu algoritma yalnızca yönlendirilmiş ağırlıklı grafikler için çalışır ve bu grafiğin tüm kenarları negatif olmamalıdır.

Dijkstra'nın algoritmasının birçok avantajı olmasına rağmen bazı dezavantajları da vardır:

1. Dijkstra Algoritması, süreç boyunca çok fazla zaman harcayan gizli bir keşif gerçekleştirir.
2. Bu algoritma negatif kenarları işleme konusunda yetersizdir.
3. Bu algoritma döngüsel olmayan grafiğe yöneldiği için en kısa yolu tam olarak hesaplayamaz.
4. Ayrıca ziyaret edilen köşelerin kaydını tutmak için bakım gerektirir.

Dijkstra Algoritmasının Bazı Uygulamaları

Dijkstra Algoritmasının, bazıları aşağıda belirtilen çeşitli gerçek dünya uygulamaları vardır:

Google Haritalar'daki Dijital Haritalama Hizmetleri:Google Haritalar'da konumumuz ile en yakın tercih edilen konum arasındaki mesafeyi veya bir şehirden diğerine olan mesafeyi bulmaya çalıştığımız çeşitli zamanlar vardır; bu, onları birbirine bağlayan birden fazla güzergah/yoldan oluşur; ancak uygulamanın minimum mesafeyi göstermesi gerekir. Bu yalnızca Dijkstra'nın algoritmasının, uygulamanın yol boyunca verilen iki konum arasındaki en kısa olanı bulmasına yardımcı olması nedeniyle mümkündür. ABD'yi şehirlerin/yerlerin köşelerle, iki şehir/yer arasındaki rotaların ise kenarlarla temsil edildiği bir grafik olarak düşünelim. Daha sonra Dijkstra Algoritması'nın yardımıyla herhangi iki şehir/yer arasındaki en kısa rotaları hesaplayabiliriz.Sosyal Ağ Uygulamaları:Facebook, Twitter, Instagram ve daha fazlası gibi birçok uygulamada, çoğumuz bu uygulamaların belirli bir kullanıcının tanıyabileceği arkadaş listesini önerdiğini gözlemlemiş olabiliriz. Özellikle sistemin bir milyardan fazla kullanıcısı varken, pek çok sosyal medya şirketi bu tür bir özelliği verimli ve etkili bir şekilde nasıl uyguluyor? Bu sorunun cevabı Dijkstra Algoritmasıdır. Standart Dijkstra Algoritması genellikle kullanıcılar arasındaki bağlantılar veya karşılıklılık yoluyla ölçülen en kısa mesafeyi tahmin etmek için kullanılır. Sosyal ağ çok küçük olduğunda en kısa yolları belirlemek için diğer bazı özelliklere ek olarak standart Dijkstra Algoritmasını kullanır. Ancak grafik çok daha büyük olduğunda standart algoritmanın sayımı birkaç saniye alır ve bu nedenle alternatif olarak bazı gelişmiş algoritmalar kullanılır.Telefon Ağı:Bazılarımızın bildiği gibi, bir telefon ağında her iletim hattının bir 'b' bant genişliği vardır. Bant genişliği, iletim hattının destekleyebileceği en yüksek frekanstır. Genel olarak belirli bir hatta sinyalin frekansı daha yüksekse sinyal o hat kadar azaltılır. Bant genişliği hat tarafından iletilebilecek bilgi miktarını temsil eder. Bir şehri, anahtarlama istasyonlarının köşeler kullanılarak temsil edildiği, iletim hatlarının kenarlar olarak temsil edildiği ve 'b' bant genişliğinin kenarların ağırlığı kullanılarak temsil edildiği bir grafik olarak düşünelim. Böylece, gözlemleyebileceğimiz gibi, telefon şebekesi de en kısa mesafe problemi kategorisine girebilir ve Dijkstra Algoritması kullanılarak çözülebilir.Uçuş Programı:Bir kişinin müşteriler için uçuş gündemi hazırlamak üzere bir yazılıma ihtiyaç duyduğunu varsayalım. Temsilcinin tüm uçuşları ve havalimanlarını içeren bir veritabanına erişimi vardır. Uçuş numarası, kalkış havaalanı ve varış yerinin yanı sıra uçuşların kalkış ve varış saatleri de vardır. Bu nedenle, seçilen varış noktasına orijinal havaalanından en erken varış zamanını ve verilen başlangıç ​​zamanını belirlemek için acenteler Dijkstra Algoritmasını kullanıyor.Önce En Kısa Yolu Aç'ı bulmak için IP yönlendirme:Önce En Kısa Yolu Aç (OSPF olarak kısaltılır), kendi Önce En Kısa Yol'un yardımıyla kaynak ve hedef yönlendirici arasındaki en iyi yolu bulmak için kullanılan bir bağlantı durumu yönlendirme protokolüdür. Dijkstra Algoritması, yönlendiricilerin yönlendirme tablolarını güncellemek için ihtiyaç duyduğu yönlendirme protokollerinde yaygın olarak kullanılmaktadır. Algoritma, kaynak yönlendiriciden ağdaki diğer yönlendiricilere giden en kısa maliyet yolunu verir.Robotik Yol:Günümüzde bazıları manuel, bazıları otomatik olarak çalışan dronelar ve robotlar ortaya çıktı. Otomatik olarak çalıştırılan ve paketleri belirli bir yere teslim etmek veya belirli bir görev için kullanılan drone ve robotlar, Dijkstra'nın Algoritma modülü ile yapılandırılarak kaynak ve hedef bilindiğinde drone ve robotun belirtilen yönde hareket etmesi sağlanır. Paketleri teslim etmek için harcanan süreyi minimumda tutarak en kısa yolu takip ederek.Dosya Sunucusunu Belirleyin:Dijkstra Algoritması aynı zamanda Yerel Alan Ağı'ndaki (LAN) bir dosya sunucusunu belirlemek için de kullanılır. Dosyaların bir bilgisayardan diğerine aktarılması için sonsuz bir süreye ihtiyaç olduğunu varsayalım. Dolayısıyla, dosya sunucusundan ağdaki diğer tüm bilgisayarlara 'atlama' sayısını en aza indirmek için Dijkstra Algoritmasını kullanacağız. Bu algoritma ağlar arasındaki en kısa yolu döndürerek minimum atlama sayısını sağlar.

Sonuç

• Yukarıdaki eğitimde öncelikle Graph'ın temel kavramlarını, türlerini ve uygulamalarını anladık.
• Daha sonra Dijkstra Algoritmasını ve tarihini öğrendik.
• Dijkstra Algoritmasının temel işleyişini de bir örnek yardımıyla anlamış olduk.
• Daha sonra Pseudocode yardımıyla Dijkstra Algoritmasına nasıl kod yazılacağını inceledik.
• C, C++, Java ve Python gibi programlama dillerinde uygun çıktılar ve açıklamalarla uygulanmasını gözlemledik.
• Dijkstra Algoritmasının Zaman ve Uzay Karmaşıklığını da anladık.
• Son olarak Dijkstra algoritmasının avantajlarını, dezavantajlarını ve gerçek hayattaki bazı uygulamalarını tartıştık.