حل خوارزمية ديكسترا (Dijkstra’s Algorithm) مع أمثلة في Python، Java، و C

1. مقدمة عن المشكلة

وصف المشكلة:
خوارزمية ديكسترا (Dijkstra’s Algorithm) هي خوارزمية مشهورة تُستخدم لإيجاد أقصر مسار بين عقدة البداية والعقد الأخرى في رسم بياني موجه ذو أوزان غير سالبة. تعتمد على مبدأ الاستكشاف التدريجي للعقد للحصول على المسار الأدنى تكلفة.

حالة استخدام:
تُستخدم خوارزمية ديكسترا في تطبيقات مثل أنظمة الملاحة، حيث يمكنها تحديد أقصر طريق بين موقعين، وفي الشبكات الحاسوبية لإيجاد المسار الأمثل لنقل البيانات.

المدخلات والمخرجات:

• المدخلات: رسم بياني ذو أوزان غير سالبة وعقدة بداية.
• المخرجات: أقصر مسافة من عقدة البداية إلى جميع العقد الأخرى.

2. شرح تعليمي للحل

خوارزمية ديكسترا تعتمد على استخدام هيكل بيانات مثل قائمة ذات أولوية (Priority Queue) لاختيار العقدة ذات المسافة الأدنى غير المستكشفة. تعتمد الخوارزمية على تحديث المسافة الأقصر لكل عقدة تدريجيًا حتى يتم إيجاد المسار الأدنى تكلفة.

• نقوم بتهيئة المسافة إلى العقدة المصدر بصفر وجميع العقد الأخرى باللانهاية.
• نستخدم قائمة ذات أولوية لتحديد العقدة ذات المسافة الأدنى غير المستكشفة.
• نحدث المسافة للعقد المجاورة للعقدة الحالية إذا وجدنا مسارًا أقصر.
• نكرر العملية حتى نستكشف جميع العقد.

تعقيد الوقت:

• O((V + E) log V)، حيث V هو عدد العقد و E هو عدد الحواف.

تعقيد المساحة:

• O(V)، حيث V هو عدد العقد لتخزين المسافات.

3. الحل في Python

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# استخدام المثال
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
print("أقصر المسافات من العقدة A:", dijkstra(graph, 'A'))

4. الحل في Java

import java.util.*;

public class Dijkstra {

    public static Map<String, Integer> dijkstra(Map<String, Map<String, Integer>> graph, String start) {
        Map<String, Integer> distances = new HashMap<>();
        for (String vertex : graph.keySet()) {
            distances.put(vertex, Integer.MAX_VALUE);
        }
        distances.put(start, 0);

        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(node -> node.distance));
        priorityQueue.add(new Node(start, 0));

        while (!priorityQueue.isEmpty()) {
            Node current = priorityQueue.poll();
            if (current.distance > distances.get(current.vertex)) continue;

            Map<String, Integer> neighbors = graph.get(current.vertex);
            for (Map.Entry<String, Integer> neighbor : neighbors.entrySet()) {
                int newDist = distances.get(current.vertex) + neighbor.getValue();
                if (newDist < distances.get(neighbor.getKey())) {
                    distances.put(neighbor.getKey(), newDist);
                    priorityQueue.add(new Node(neighbor.getKey(), newDist));
                }
            }
        }

        return distances;
    }

    static class Node {
        String vertex;
        int distance;

        Node(String vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }
    }

    public static void main(String[] args) {
        Map<String, Map<String, Integer>> graph = new HashMap<>();
        graph.put("A", Map.of("B", 1, "C", 4));
        graph.put("B", Map.of("A", 1, "C", 2, "D", 5));
        graph.put("C", Map.of("A", 4, "B", 2, "D", 1));
        graph.put("D", Map.of("B", 5, "C", 1));

        System.out.println("أقصر المسافات من العقدة A: " + dijkstra(graph, "A"));
    }
}

5. الحل في C

#include <stdio.h>
#include <limits.h>
#define V 4

int minDistance(int dist[], int sptSet[]) {
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (sptSet[v] == 0 && dist[v] <= min)
            min = dist[v], min_index = v;

    return min_index;
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    int sptSet[V];

    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = 0;

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = 1;

        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
                && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    printf("العقدة \\t المسافة من المصدر\\n");
    for (int i = 0; i < V; i++)
        printf("%d \\t\\t %d\\n", i, dist[i]);
}

int main() {
    int graph[V][V] = { {0, 1, 4, 0},
                        {1, 0, 2, 5},
                        {4, 2, 0, 1},
                        {0, 5, 1, 0} };

    dijkstra(graph, 0);

    return 0;
}