Algartam Dijkstra agus a chur i bhfeidhm

Tá áit ar leith ar a dtugtar teoiric graf sa mhatamaitic agus san eolaíocht ríomhaireachta. Mar chuid dá leagan síos agus chun fadhbanna éagsúla, mar shampla a aimsiú ar an cosán is giorra idir na reanna réiteach. Amháin coitianta i measc bealaí matamaiticeoirí den réiteach ar an bhfadhb le fada algartam ina Dijkstra ar.

Cad is graf matamaiticiúla

Tá sé Creidtear go raibh an coincheap den ghraf a chur in úsáid sa ochtú haois Leonardom Eylerom. Ba é an té a d'fhógair a cheapadh agus a réiteach ar cheann de na fadhbanna clasaiceach an teoiric - na seacht droichid na Königsberg. Chun míniú a thabhairt ar an cuspóir an teoiric a úsáid go minic an analaí le gluaiseacht idir cathracha éagsúla. Ansin, beidh an graf ar an eitleán a bheith ina léaráid fad bealach, nuair a bheith rinn nithe ar leith (m.sh., cathracha), agus ar na himill - cosán ó rinn amháin go ceann eile (bóthar aschur idir cathracha). algartam Dijkstra ar, chomh maith le modhanna eile is féidir, a chur ar fáil ar réiteach ar an gceist seo.

Lorg an cosán is giorra

Ceann de na tascanna comónta de teoiric graf Tá ceann ina bhfuil gá duit a chinneadh an cosán fearr is féidir costas idir dhá phointe. Is féidir leis an eitleán a laghdú leis an gcinneadh an ghraif ina bhfuil na reanna - Tá easnacha idirnasctha, a bhfuil bóthar is féidir - cathracha. Tá gach bóthar a fhad féin, mar sin, taisteal ar é a bheidh a chaitheamh roinnt airgid. Tá an méid is ionann agus an meáchan ar an imill sa ghraf. Ansin, is féidir leis an bhfadhb i gcleachtas a chur le chéile mar seo a leanas: conas a réiteach ar an mbealach ó chathair amháin go ceann eile, le caitheamh ar an íosmhéid mbóthar acmhainne.

bhealaí chun an fhadhb

Chun fhadhb seo a réiteach mór dúinn a bheith invented ag roinnt halgartaim a tháinig chun bheith ar eolas go forleathan ar fud an domhain eolaíochta. Mar shampla, Floyd algartam - Uorshella, Ford - Bellman. Is é an bealach clasaiceach de réitigh a fháil chomh maith algartam Dijkstra ar. Is féidir é a úsáid le haghaidh ualaithe (ar a dtugtar meáchan ar gach imeall) den ghraf, agus a chaolú. Chun teacht ar an bealach deiridh mór duit a dhéanamh ar roinnt céimeanna.

algartam Dijkstra ar

Tá an pointe an modh seo ar an bhfíric go bhfuil na reanna costais, ag tosú le ar leith, wherein gach chlib sannadh luach áirithe. Ansin, beidh san áireamh leis toradh na stuaiceanna a bhfuil a lipéid tá íosta. Ar Beidh bharr an chéad chéim tosaigh a bhfuil clib le luach de 0. Ansin, gach ceann de na beanna seo a leanas a mheas, is é sin, iad siúd is féidir a bheith bainte amach ón bhfoinse. Tá siad lipéadaithe, tá a luach mar shuim an cód foinse agus meáchan na cosáin. Ó barr an chéad chéim eile, roghnaigh an ceann a thug an luach is lú an lipéid, agus rinne sé staidéar ar na reanna sa mhéid is go as é is féidir linn dul gan úsáid a bhaint na nóid idirmheánach. Sonraigh lipéad nua comhionann leis an bharr lipéid - cód foinse móide meáchan an mbealach. Má tá an luach níos lú ná an lipéad barr, tá an lipéad a athrú. Seachas sin, tá sé fós an luach bunaidh. Ag an am céanna i sraith ar leith, a bhfuil a gné is comhionann leis an líon na reann, siopaí sé mar thoradh ar leas iomlán a bhaint, ina bhfuil agus ar bhealach diongbháilte. Chun modh a chur i bhfeidhm, mar shampla algartam Dijkstra, cuireann Pascal bealach an-áisiúil. Tá an algartam an buntáiste gur féidir é a bheith go héasca ar an bonn le haghaidh clár go bhfuil méid beag. Samplaí de tháirgí bhogearraí den sórt sin éasca a fháil ar an Idirlíon.

réitigh dle uirlisí éagsúla is féidir leat é a úsáid ar an tasc a fháil ar an cosán is fearr is féidir. I gcás réitigh nós algartam Dijkstra ar, beidh Delphi chruthú foirm áisiúil d'ionchur sonraí amhairc agus aschur an toradh deiridh.