Dijkstra ta algorithm kuma da aiwatar

Akwai raba yankin kira jadawali ka'idar a ilmin lissafi da kuma kimiyyar kwamfuta. Kamar yadda wani ɓangare na da sa da kuma warware matsaloli daban-daban, kamar gano da guntu hanya tsakanin vertices. Daya kowa daga lissafi hanyoyi na warware wannan matsalar ya dade a Dijkstra ta algorithm.

Mene ne a ilmin lissafi jadawali

An yi imani da cewa mas'ala ta da jadawali da aka sa a cikin yin amfani a karni na sha takwas Leonardom Eylerom. Shi ya sanar da halitta da kuma bayani na daya daga cikin classic matsaloli na wannan ka'idar - bakwai gadoji na Königsberg. Domin bayyana abu na wannan ka'idar sau da yawa amfani da wannan misalin a matsayin motsi tsakanin daban-daban birane. Sai jadawali a kan jirgin zai zama wani dukan hanya zane, inda vertices zama takamaiman abubuwa (msl, birane), da kuma gefuna - hanya daga daya kokuwa zuwa wani (analog hanya tsakanin birane). Dijkstra ta algorithm, ban da wasu hanyoyin, za a iya samar da wani bayani ga wannan batu.

Samun guntu hanya

Daya daga cikin na kowa ayyuka na jadawali ka'idar ne daya a cikin abin da za ka bukatar sanin da mafi kyau duka kudin hanya tsakanin maki biyu. Yana yiwuwa a rage jirgin sama zuwa da shawarar da jadawali a cikin abin da vertices - birane - suna juna hakarkarinsa, wanda shi ne mai yiwu hanya. Kowane hanya na da tsawon, saboda haka, tafiya a kan shi zai yi don ciyar da wasu kudi. Wannan adadin shi ne daidai da nauyin da gefuna a cikin jadawali. Sa'an nan matsalar a yi za a iya tsara kamar haka: yadda za a sa a kan hanya, daga wannan garin zuwa wani, za a kashe a kan hanya m wajen.

hanyoyin da za a magance

Don warware wannan matsala da muke da aka ƙirƙira by wasu Algorithms cewa sun zama yadu da aka sani a duniyar kimiyya. Alal misali, Floyd algorithm - Uorshella, Hyundai - Bellman. A classic hanyar samar da mafita ne kuma Dijkstra ta algorithm. Ana iya amfani da wa mai nauyi (da aka sani nauyi na kowane gefe) na jadawali, kuma zuwa tsarma. Don samun matuƙar hanya dole ne ka yi da dama matakai.

Dijkstra ta algorithm

A batu na wannan hanya ta'allaka ne da cewa duk da vertices na kudin, da tafara da ba, a cikinta kowane tag an sanya wani daraja. Sa'an nan sakamakon zai hada da vertices wanda tasirin ne kadan. A saman na farko farko mataki za a tagged da darajar 0. Sa'an nan, duk wadannan kololuwa suna dauke, wato, waɗanda za a iya isa daga Madogararsa. Suna labeled, da darajar da aka ƙaddara a matsayin Naira Miliyan Xari da tushen code da kuma nauyi na hanyoyi. Daga saman mataki na gaba, zaɓi daya cewa yana da karami darajar da lakabin, kuma karatu duk da vertices a cewa daga gare shi ba za mu iya tafiya ba tare da amfani da tsaka-tsaki nodes. Saka wani sabon lakabin daidaita da lakabin fi - tushen code da nauyin hanya. Idan darajar ne kasa da saman lakabin, lakabin da aka canza. In ba haka ba, za ta zauna da asali darajar. A lokaci guda a raba tsararru, wadanda girma ne daidai da adadin vertices, shi Stores sakamakon ingantawa, a cikin abin da kuma suka yi niyya hanya. Don aiwatar da wani Hanyar kamar Dijkstra ta algorithm, Pascal yayi wani sosai dace wajen. A algorithm yana da amfani cewa shi iya zama dalilin wani shirin cewa yana da wani kananan size. Misalai na irin wannan software kayayyakin sauki sami a kan Internet.

Dle mafita daban-daban kayan aikin da za ka iya amfani da aiki a sami mafi kyau duka hanya. Domin mafita kamar Dijkstra ta algorithm, Delphi zai haifar da m nau'i na gani data shigar da fitarwa karshe sakamakon.