الگوریتم دایجسترا (Dijkstra) — از صفر تا صد

1// A C++ program for Dijkstra's single source shortest path algorithm. 
2// The program is for adjacency matrix representation of the graph 
3   
4#include <stdio.h> 
5#include <limits.h> 
6   
7// Number of vertices in the graph 
8#define V 9 
9   
10// A utility function to find the vertex with minimum distance value, from 
11// the set of vertices not yet included in shortest path tree 
12int minDistance(int dist[], bool sptSet[]) 
13{ 
14   // Initialize min value 
15   int min = INT_MAX, min_index; 
16   
17   for (int v = 0; v < V; v++) 
18     if (sptSet[v] == false && dist[v] <= min) 
19         min = dist[v], min_index = v; 
20   
21   return min_index; 
22} 
23   
24// A utility function to print the constructed distance array 
25int printSolution(int dist[], int n) 
26{ 
27   printf("Vertex   Distance from Source\n"); 
28   for (int i = 0; i < V; i++) 
29      printf("%d tt %d\n", i, dist[i]); 
30} 
31   
32// Function that implements Dijkstra's single source shortest path algorithm 
33// for a graph represented using adjacency matrix representation 
34void dijkstra(int graph[V][V], int src) 
35{ 
36     int dist[V];     // The output array.  dist[i] will hold the shortest 
37                      // distance from src to i 
38   
39     bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest 
40                     // path tree or shortest distance from src to i is finalized 
41   
42     // Initialize all distances as INFINITE and stpSet[] as false 
43     for (int i = 0; i < V; i++) 
44        dist[i] = INT_MAX, sptSet[i] = false; 
45   
46     // Distance of source vertex from itself is always 0 
47     dist[src] = 0; 
48   
49     // Find shortest path for all vertices 
50     for (int count = 0; count < V-1; count++) 
51     { 
52       // Pick the minimum distance vertex from the set of vertices not 
53       // yet processed. u is always equal to src in the first iteration. 
54       int u = minDistance(dist, sptSet); 
55   
56       // Mark the picked vertex as processed 
57       sptSet[u] = true; 
58   
59       // Update dist value of the adjacent vertices of the picked vertex. 
60       for (int v = 0; v < V; v++) 
61   
62         // Update dist[v] only if is not in sptSet, there is an edge from  
63         // u to v, and total weight of path from src to  v through u is  
64         // smaller than current value of dist[v] 
65         if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX  
66                                       && dist[u]+graph[u][v] < dist[v]) 
67            dist[v] = dist[u] + graph[u][v]; 
68     } 
69   
70     // print the constructed distance array 
71     printSolution(dist, V); 
72} 
73   
74// driver program to test above function 
75int main() 
76{ 
77   /* Let us create the example graph discussed above */
78   int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0}, 
79                      {4, 0, 8, 0, 0, 0, 0, 11, 0}, 
80                      {0, 8, 0, 7, 0, 4, 0, 0, 2}, 
81                      {0, 0, 7, 0, 9, 14, 0, 0, 0}, 
82                      {0, 0, 0, 9, 0, 10, 0, 0, 0}, 
83                      {0, 0, 4, 14, 10, 0, 2, 0, 0}, 
84                      {0, 0, 0, 0, 0, 2, 0, 1, 6}, 
85                      {8, 11, 0, 0, 0, 0, 1, 0, 7}, 
86                      {0, 0, 2, 0, 0, 0, 6, 7, 0} 
87                     }; 
88   
89    dijkstra(graph, 0); 
90   
91    return 0; 
92}

1// A Java program for Dijkstra's single source shortest path algorithm. 
2// The program is for adjacency matrix representation of the graph 
3import java.util.*; 
4import java.lang.*; 
5import java.io.*; 
6  
7class ShortestPath 
8{ 
9    // A utility function to find the vertex with minimum distance value, 
10    // from the set of vertices not yet included in shortest path tree 
11    static final int V=9; 
12    int minDistance(int dist[], Boolean sptSet[]) 
13    { 
14        // Initialize min value 
15        int min = Integer.MAX_VALUE, min_index=-1; 
16  
17        for (int v = 0; v < V; v++) 
18            if (sptSet[v] == false && dist[v] <= min) 
19            { 
20                min = dist[v]; 
21                min_index = v; 
22            } 
23  
24        return min_index; 
25    } 
26  
27    // A utility function to print the constructed distance array 
28    void printSolution(int dist[], int n) 
29    { 
30        System.out.println("Vertex   Distance from Source"); 
31        for (int i = 0; i < V; i++) 
32            System.out.println(i+" tt "+dist[i]); 
33    } 
34  
35    // Funtion that implements Dijkstra's single source shortest path 
36    // algorithm for a graph represented using adjacency matrix 
37    // representation 
38    void dijkstra(int graph[][], int src) 
39    { 
40        int dist[] = new int[V]; // The output array. dist[i] will hold 
41                                 // the shortest distance from src to i 
42  
43        // sptSet[i] will true if vertex i is included in shortest 
44        // path tree or shortest distance from src to i is finalized 
45        Boolean sptSet[] = new Boolean[V]; 
46  
47        // Initialize all distances as INFINITE and stpSet[] as false 
48        for (int i = 0; i < V; i++) 
49        { 
50            dist[i] = Integer.MAX_VALUE; 
51            sptSet[i] = false; 
52        } 
53  
54        // Distance of source vertex from itself is always 0 
55        dist[src] = 0; 
56  
57        // Find shortest path for all vertices 
58        for (int count = 0; count < V-1; count++) 
59        { 
60            // Pick the minimum distance vertex from the set of vertices 
61            // not yet processed. u is always equal to src in first 
62            // iteration. 
63            int u = minDistance(dist, sptSet); 
64  
65            // Mark the picked vertex as processed 
66            sptSet[u] = true; 
67  
68            // Update dist value of the adjacent vertices of the 
69            // picked vertex. 
70            for (int v = 0; v < V; v++) 
71  
72                // Update dist[v] only if is not in sptSet, there is an 
73                // edge from u to v, and total weight of path from src to 
74                // v through u is smaller than current value of dist[v] 
75                if (!sptSet[v] && graph[u][v]!=0 && 
76                        dist[u] != Integer.MAX_VALUE && 
77                        dist[u]+graph[u][v] < dist[v]) 
78                    dist[v] = dist[u] + graph[u][v]; 
79        } 
80  
81        // print the constructed distance array 
82        printSolution(dist, V); 
83    } 
84  
85    // Driver method 
86    public static void main (String[] args) 
87    { 
88        /* Let us create the example graph discussed above */
89       int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0}, 
90                                  {4, 0, 8, 0, 0, 0, 0, 11, 0}, 
91                                  {0, 8, 0, 7, 0, 4, 0, 0, 2}, 
92                                  {0, 0, 7, 0, 9, 14, 0, 0, 0}, 
93                                  {0, 0, 0, 9, 0, 10, 0, 0, 0}, 
94                                  {0, 0, 4, 14, 10, 0, 2, 0, 0}, 
95                                  {0, 0, 0, 0, 0, 2, 0, 1, 6}, 
96                                  {8, 11, 0, 0, 0, 0, 1, 0, 7}, 
97                                  {0, 0, 2, 0, 0, 0, 6, 7, 0} 
98                                 }; 
99        ShortestPath t = new ShortestPath(); 
100        t.dijkstra(graph, 0); 
101    } 
102} 
103//This code is contributed by Aakash Hasija

1// A C# program for Dijkstra's single  
2// source shortest path algorithm. 
3// The program is for adjacency matrix 
4// representation of the graph 
5using System;  
6  
7class GFG 
8{ 
9// A utility function to find the  
10// vertex with minimum distance 
11// value, from the set of vertices 
12// not yet included in shortest  
13// path tree 
14static int V = 9; 
15int minDistance(int[] dist,  
16                bool[] sptSet) 
17{ 
18    // Initialize min value 
19    int min = int.MaxValue, min_index = -1; 
20  
21    for (int v = 0; v < V; v++) 
22        if (sptSet[v] == false &&  
23              dist[v] <= min) 
24        { 
25            min = dist[v]; 
26            min_index = v; 
27        } 
28  
29    return min_index; 
30} 
31  
32// A utility function to print 
33// the constructed distance array 
34void printSolution(int[] dist, int n) 
35{ 
36    Console.Write("Vertex     Distance " +  
37                        "from Source\n"); 
38    for (int i = 0; i < V; i++) 
39        Console.Write(i + " \t\t " +  
40                    dist[i] + "\n"); 
41} 
42  
43// Funtion that implements Dijkstra's  
44// single source shortest path algorithm 
45// for a graph represented using adjacency  
46// matrix representation 
47void dijkstra(int[,] graph, int src) 
48{ 
49    int[] dist = new int[V]; // The output array. dist[i] 
50                             // will hold the shortest  
51                             // distance from src to i 
52  
53    // sptSet[i] will true if vertex 
54    // i is included in shortest path  
55    // tree or shortest distance from  
56    // src to i is finalized 
57    bool[] sptSet = new bool[V]; 
58  
59    // Initialize all distances as  
60    // INFINITE and stpSet[] as false 
61    for (int i = 0; i < V; i++) 
62    { 
63        dist[i] = int.MaxValue; 
64        sptSet[i] = false; 
65    } 
66  
67    // Distance of source vertex 
68    // from itself is always 0 
69    dist[src] = 0; 
70  
71    // Find shortest path for all vertices 
72    for (int count = 0; count < V - 1; count++) 
73    { 
74        // Pick the minimum distance vertex  
75        // from the set of vertices not yet  
76        // processed. u is always equal to  
77        // src in first iteration. 
78        int u = minDistance(dist, sptSet); 
79  
80        // Mark the picked vertex as processed 
81        sptSet[u] = true; 
82  
83        // Update dist value of the adjacent  
84        // vertices of the picked vertex. 
85        for (int v = 0; v < V; v++) 
86  
87            // Update dist[v] only if is not in  
88            // sptSet, there is an edge from u  
89            // to v, and total weight of path  
90            // from src to v through u is smaller  
91            // than current value of dist[v] 
92            if (!sptSet[v] && graph[u, v] != 0 && 
93                       dist[u] != int.MaxValue && 
94                 dist[u] + graph[u, v] < dist[v]) 
95                dist[v] = dist[u] + graph[u, v]; 
96    } 
97  
98    // print the constructed distance array 
99    printSolution(dist, V); 
100} 
101  
102// Driver Code 
103public static void Main () 
104{ 
105/* Let us create the example  
106graph discussed above */
107int[,] graph = new int[,]{{0, 4, 0, 0, 0, 0, 0, 8, 0}, 
108                          {4, 0, 8, 0, 0, 0, 0, 11, 0}, 
109                          {0, 8, 0, 7, 0, 4, 0, 0, 2}, 
110                          {0, 0, 7, 0, 9, 14, 0, 0, 0}, 
111                          {0, 0, 0, 9, 0, 10, 0, 0, 0}, 
112                          {0, 0, 4, 14, 10, 0, 2, 0, 0}, 
113                          {0, 0, 0, 0, 0, 2, 0, 1, 6}, 
114                          {8, 11, 0, 0, 0, 0, 1, 0, 7}, 
115                          {0, 0, 2, 0, 0, 0, 6, 7, 0}}; 
116    GFG t = new GFG(); 
117    t.dijkstra(graph, 0); 
118} 
119} 
120  
121// This code is contributed by ChitraNayal

1# Python program for Dijkstra's single  
2# source shortest path algorithm. The program is  
3# for adjacency matrix representation of the graph 
4  
5# Library for INT_MAX 
6import sys 
7  
8class Graph(): 
9  
10    def __init__(self, vertices): 
11        self.V = vertices 
12        self.graph = [[0 for column in range(vertices)]  
13                      for row in range(vertices)] 
14  
15    def printSolution(self, dist): 
16        print "Vertex tDistance from Source"
17        for node in range(self.V): 
18            print node,"t",dist[node] 
19  
20    # A utility function to find the vertex with  
21    # minimum distance value, from the set of vertices  
22    # not yet included in shortest path tree 
23    def minDistance(self, dist, sptSet): 
24  
25        # Initilaize minimum distance for next node 
26        min = sys.maxint 
27  
28        # Search not nearest vertex not in the  
29        # shortest path tree 
30        for v in range(self.V): 
31            if dist[v] < min and sptSet[v] == False: 
32                min = dist[v] 
33                min_index = v 
34  
35        return min_index 
36  
37    # Funtion that implements Dijkstra's single source  
38    # shortest path algorithm for a graph represented  
39    # using adjacency matrix representation 
40    def dijkstra(self, src): 
41  
42        dist = [sys.maxint] * self.V 
43        dist[src] = 0
44        sptSet = [False] * self.V 
45  
46        for cout in range(self.V): 
47  
48            # Pick the minimum distance vertex from  
49            # the set of vertices not yet processed.  
50            # u is always equal to src in first iteration 
51            u = self.minDistance(dist, sptSet) 
52  
53            # Put the minimum distance vertex in the  
54            # shotest path tree 
55            sptSet[u] = True
56  
57            # Update dist value of the adjacent vertices  
58            # of the picked vertex only if the current  
59            # distance is greater than new distance and 
60            # the vertex in not in the shotest path tree 
61            for v in range(self.V): 
62                if self.graph[u][v] > 0 and sptSet[v] == False and 
63                   dist[v] > dist[u] + self.graph[u][v]: 
64                        dist[v] = dist[u] + self.graph[u][v] 
65  
66        self.printSolution(dist) 
67  
68# Driver program 
69g  = Graph(9) 
70g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0], 
71           [4, 0, 8, 0, 0, 0, 0, 11, 0], 
72           [0, 8, 0, 7, 0, 4, 0, 0, 2], 
73           [0, 0, 7, 0, 9, 14, 0, 0, 0], 
74           [0, 0, 0, 9, 0, 10, 0, 0, 0], 
75           [0, 0, 4, 14, 10, 0, 2, 0, 0], 
76           [0, 0, 0, 0, 0, 2, 0, 1, 6], 
77           [8, 11, 0, 0, 0, 0, 1, 0, 7], 
78           [0, 0, 2, 0, 0, 0, 6, 7, 0] 
79          ]; 
80  
81g.dijkstra(0); 
82  
83# This code is contributed by Divyanshu Mehta