Жонсон алгоритмісі: бағытталған графтардағы ең қысқа жолдарды табу, теріс салмақтарды жою, Bellman-Ford және Dijkstra алгоритмдерін қолдану. Компьютерлік жол табу әдісі.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік жол табу әдісі
Computer based path finding method
сол аттас жоспарлау алгоритмі
the scheduling algorithm of the same name
Джонсон алгоритмі – бұл шеттері салмақталған бағытталған графтың барлық төбелері арасындағы ең қысқа жолдарды табу тәсілі. Бұл кейбір шеттік салмақтардың теріс сандар болуына мүмкіндік береді, бірақ теріс салмақты циклдар болмауы керек. Ол Bellman-Ford алгоритмін пайдаланып, кіріс графты кері өзгерту арқылы жұмыс істейді, бұл барлық теріс салмақтарды жояды және өзгертілген графқа Дикстра алгоритмін қолдануға мүмкіндік береді. Бұл техниканы алғаш 1977 жылы жариялаған Дональд Б. Джонсонның құрметіне аталған. Сурбалл алгоритмінде де ұқсас қайта салмақтау тәсілі қолданылады, ол теріс емес шеттік салмақтары бар графтың бірдей екі төбесі арасындағы ең аз жалпы ұзындығы бар екі бөлек жолды табу үшін пайдаланылады.
Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in an edge weighted directed graph. It allows some of the edge weights to be negative numbers, but no negative weight cycles may exist. It works by using the Bellman–Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra's algorithm to be used on the transformed graph. It is named after Donald B. Johnson, who first published the technique in 1977. A similar reweighting technique is also used in Suurballe's algorithm for finding two disjoint paths of minimum total length between the same two vertices in a graph with non negative edge weights.
Мысал
Джонсон алгоритмінің алғашқы үш кезеңі төмендегі суретте көрсетілген. Суреттің сол жағындағы граф екі теріс қабырғаға ие, бірақ теріс цикл жоқ. Ортадағы граф жаңа q төбесін, Bellman-Ford алгоритмімен есептелген ең қысқа жол ағашын (q бастапқы төбе ретінде) және әрбір төбеге q-дан сол төбеге дейінгі ең қысқа жол ұзындығы ретінде есептелген h(v) мәндерін көрсетеді. Бұл мәндердің барлығы оң емес екенін ескеріңіз, себебі q-дан әрбір төбеге нөлдік ұзындықта қабырға бар, ал ең қысқа жол осы қабырғадан ұзын болмайды. Оң жақта, әр қабырға салмағын w(u,v) w(u,v) + h(u) − h(v) арқылы алмастыру арқылы құрылған қайта салмақталған граф көрсетілген. Бұл қайта салмақталған графта барлық қабырға салмақтары теріс емес, бірақ кез келген екі төбе арасындағы ең қысқа жол бастапқы графтағы сол екі төбе арасындағы ең қысқа жолмен бірдей қабырғалар тізбесін пайдаланады. Алгоритм қайта салмақталған графтағы төрт бастапқы төбеге Дикстра алгоритмін қолдану арқылы аяқталады.
The first three stages of Johnson's algorithm are depicted in the illustration below. The graph on the left of the illustration has two negative edges, but no negative cycles. The center graph shows the new vertex q, a shortest path tree as computed by the Bellman–Ford algorithm with q as starting vertex, and the values h(v) computed at each other node as the length of the shortest path from q to that node. Note that these values are all non positive, because q has a length zero edge to each vertex and the shortest path can be no longer than that edge. On the right is shown the reweighted graph, formed by replacing each edge weight w(u,v) by w(u,v) + h(u) − h(v). In this reweighted graph, all edge weights are non negative, but the shortest path between any two nodes uses the same sequence of edges as the shortest path between the same two nodes in the original graph. The algorithm concludes by applying Dijkstra's algorithm to each of the four starting nodes in the reweighted graph.
Талдау
Фибоначчи үйінділерін қолдана отырып, Дикстра алгоритмін іске асырудағы осы алгоритмнің уақыт күрделілігі: алгоритм алгоритмнің Беллман-Форд кезеңіне және Дикстра алгоритмінің әрбір орындалуына уақыт жұмсайды. Осылайша, егер граф сирең болса, жалпы уақыт Флойд-Варшалл алгоритмінен тез болуы мүмкін, ол осы мәселені уақытта шешеді.
The time complexity of this algorithm, using Fibonacci heaps in the implementation of Dijkstra's algorithm, is : the algorithm uses time for the Bellman–Ford stage of the algorithm, and for each of the instantiations of Dijkstra's algorithm. Thus, when the graph is sparse, the total time can be faster than the Floyd–Warshall algorithm, which solves the same problem in time .