Dijkstra’s Shortest Distance Connecting Lebanese Urban Centers138
Ali-Talal Haidar – Ali Khyami
العدد الربع عشر – آب أغسطس 2023
Pages 75-93
Abstract
A network is a system of interconnected elements affecting communication, transportation, and the flow of energy and materials (electricity, water…). Networks can be embodied as a set of nodes representing spatial locations, and a set of links representing connections. The Dijkstra’s algorithm finds the shortest path between two or more points. Paths with no intersections are usually used to map the connectivity of a network where interference may occur between its different intersecting elements. Such maps were produced for Lebanese urban centers at both the scale of the whole Lebanon, and that of each of its provinces (mouhafazat). The chosen grid size was reduced to completely avoid intersections, but kept large enough to allow for a feasible computational time. Summary statistics for the various parameters (average distance …) were inferred for the resulting networks with shortest paths. The Mount Lebanon mouhafaza shows the longest total shortest path, and that of Baalbek – Hermel has the sparsest clustering of urban centers. The produced maps of shortest paths constitute a fundamental basis for the development of any interference network type in Lebanon, especially considering the large development opportunities in the country.
Keywords: Cold Spot, Dijkstra’s Algorithm, Lebanon, Network analyst, Grid Size, shortest Path, Traveling Salesman Problem (TSP).أقصر مسافة ( Dijkstra) تربط النطاقات العمرانية اللبنانية
الشبكة هي نظام من العناصر المترابطة فيما بينها يؤثر في الاتصالات والنقل وتدفق الطاقة (كهرباء ...). تتضمن الشبكات مجموعة من العقد التي تمثل مواقع مكانية، ومجموعة من الروابط التي تمثل الموصلات. تعثر خوارزمية ( Dijkstra )على أقصر مسار بين نقطتين أو أكثر. تُستخدم عادةً المسارات التي لا تحتوي على تقاطعات لرصد موصليّة شبكة ما، حيث يمكن أن يحدث تداخل بين عناصرها المتقاطعة المختلفة. تم إعداد هذه الخرائط لمراكز النطاقات العمرانية اللبنانية على مستوى لبنان كلّه ، وعلى مستوى كل محافظة من محافظاته. تم تصغير قياس وحدة الشبكة المعتمدة لتجنّب وجود تقاطعات في المسارات، ومع المحافظة على أن يكون القياس كبيرًا بما يسمح في وقت حسابي ممكن. تم استنتاج إحصاءات موجزة للمتغيّرات المختلفة (متوسط المسافة ...) للشبكات الناتجة ذات المسارات الأقصر. تُظهر محافظة جبل لبنان أطول مسافة إجماليّة للمسار الأقصر، أما تجمّعات النطاقات العمرانية لمحافظة بعلبك - الهرمل فهي الأكثر تبعثرًا. تشكل الخرائط المنتجة لأقصر المسارات أساسًا مهمًّا لتطوير أي نوع من الشبكات في لبنان، لا سيما بالنظر إلى فرص التنمية الكبيرة في البلاد.
الكلمات المفاتيح الكلمات المفاتيح البقع الباردة، شبكة الاتصالات، خوارزمية (Dijkstra)، لبنان، محلّل الشبكات، قياس الشبكة، أقصر مسار، مسألة البائع المتجول.
