» »

DIJKSTROV_ALGORITEM

DIJKSTROV_ALGORITEM

Andro_1 ::

Zdravo,
Rad bi naredil dijkstrov algoritem vendar se ne znajdem in bi prosil za pomoč.
psevdokod algoritma:

procedure DIJKSTROV_ALGORITEM(G, s)
begin
for each vozlišče v ∈ G.V do
begin
d[v] := ∞
predhodnik[v] := NIL
end
d[s] := 0
VSTAVI_VSA_VOZLIŠČA(Q, G.V)
while not(PRAZNA(Q)) do
begin
u := IZLOČI_NAJMANJŠEGA(Q)
for each vozlišče v ∈ G.Sosedi(u) do
if d[v] > d[u] + G.P[(u, v)].utež then
begin
d[v] := d[u] + G.P[(u, v)].utež
predhodnik[v] := u
end
end
end

Za izdelavo prioritetne vrste Q bomo uporabili polje števil, ki ga bomo po vsakem
koraku uredili s pomočjo algoritma za hitro urejanje.


Bi prosil za pomoč,
Hvala lepa za odgovor!

genesiss ::

Ok. Kaj je tvoj problem?

amacar ::

Glej js sm ti zdej napisal kodo, upam da dela sm bolj na hitrco spacal skup,
popravit še morš une podatke ko so za vnos, ker nimaš ok pogoje če pod 0 al pa večje
od velikosti grafa vnese, pa svoj quicksort dodat, mogoč še izpis poti,
ker se mi to niti ne da več gledat.
 
 // ConsoleApplication1.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
  
int velikost;
int C[30][30];
  
void beri(string f)
{
  fstream dat(f.c_str(), fstream::in);
  dat >> velikost;
  int i=0;
  int p, q, c;
  
  while(!dat.eof())
  {
    dat >> p >> q >> c;
    C[p-1][q-1] = c;
    C[q-1][p-1] = c;
    i++;
  }
  dat.close();
}
  
struct Vozlisce
{
    int ime;
    int predhodnik;
    int dolzina;
};
  
void Sortiranje(vector<Vozlisce>&Q){   
    for(int i=0;i<Q.size()-1;i++){
        for(int j=0;j<Q.size()-1;j++){
            if(Q[j].dolzina > Q[j+1].dolzina){
                Vozlisce temp = Q[j];
                Q[j] = Q[j+1];
                Q[j+1] = temp;
            }
        }
    }
}
  
void DIJSKTRA(Vozlisce *G, int start){
    vector<Vozlisce> Q;
      
    for(int i=0;i<velikost;i++){
        G[i].ime=i;
        G[i].dolzina=9999;
        G[i].predhodnik=-1;
    }
    G[start].dolzina=0;
      
    for(int i=0;i<velikost;i++){ //VSTAVI_VSA_VOZLISCA(Q, G.V)
        Q.push_back(G[i]);
    }
     
    while (!Q.empty()){
        Sortiranje(Q);
        Vozlisce u = Q.front(); //IZLOCI_NAJMANJSEGA(Q)
        Q.erase(Q.begin());
        for(int i=0;i<velikost;i++){
            if(C[u.ime][i]>0){ //je sosed
                if(G[i].dolzina>G[u.ime].dolzina+C[u.ime][i]){
                    G[i].dolzina=G[u.ime].dolzina+C[u.ime][i];
                    G[i].predhodnik=G[u.ime].ime;
                    for(int j=0;j<Q.size();j++){
                        if(Q[j].ime==i){
                            Q[j].dolzina=G[u.ime].dolzina+C[u.ime][i];
                        }
                    }
                }
            }
        }
    }
}
  
void IZPIS_POTI(Vozlisce *G, int start, int konec)
{
    if(konec==start)
    {
        cout<<"Dolzina poti do vozlisca Start: "<<start<<" je "<<G[start].dolzina<<endl<<endl;
    }
    else if (G[konec].predhodnik==-1)
    {
        cout<<"Med Vozliscem "<<start<<" in vozliscem"<<konec<<" Ni poti! "<<endl<<endl;
    }
    else{
            IZPIS_POTI(G, start, G[konec].predhodnik);
            cout<<"Dolzina: "<<G[konec].dolzina<<endl;
        }
    }
  
  
int main()
{
    //system( "color 90" );
    int izbira;
    Vozlisce *G=NULL;
    int start;
    int konec;
          
    do
    {
        cout<<"  Dijkstrov algoritem - izbira: "<<endl<<endl;
        cout<<"1 Nalozi graf "<<endl;
        cout<<"2 Zagon algoritma "<<endl;
        cout<<"3 Izpis najkrajse poti "<<endl;
        cout<<"4 Konec "<<endl;
        cout<<endl;
  
        cout<<"Vasa izbira: ";
        cin>>izbira;
  
        switch (izbira)
        {
            case 1:
            {
                beri("graf.txt");
          
                G = new Vozlisce[velikost];
                cout<<"Branje Grafa je Koncano"<<endl<<endl;
  
            } ; break;
            case 2:
            {
                cout<<"Vnesite vozlisce Start: ";
                cin>>start;
                if(start<0){
                    cout<<"Ponovno izberite opcijo 2 iz menija in vnesite primerne parametre "<<endl<<endl<<endl;
                }
                else{
                    DIJSKTRA(G, start);
                }
            } break;
            case 3:
            {
                cout<<"Vnesi vozlisce Konec "<<endl;
                cin>>konec;
                if(konec<0 && konec>=velikost-1){
                    cout<<"Ponovno izberite opcijo 3 iz menija in vnesite primerne parametre "<<endl<<endl<<endl;
                }
                else
                IZPIS_POTI(G, start, konec);
            } break;
            default:
            {
                delete [] G;
            } break;
        }
    }
    while(izbira!=4);
  
    return 0;
}


placilo na trr ali paypal prek ZS :D

Andro_1 ::

Hvala,
ampak za vrsto Q bi moralz poljem, ker imam tudi algoritem za sortiranje z poljem..

amacar ::

Spremeni vektor v polje. "Tatezji" del imas ze narejen.

lebdim ::

Če je to za predmet APS, potem pomoje ni treba prav programirati tega algoritma. Važno da veš, da je v ozadju prioritetna vrsta in da veš, kako poteka. V izpitu boš imel podan konkreten graf z več vozlišči, na katerem boš moral kaj dobit po Dikstrovem algoritmu.

Zgodovina sprememb…

  • spremenil: lebdim ()

Andro_1 ::

Predmet se imenuje Osnove Algoritmov, in rabimo narediti ta program, da ga kasneje na vajah profesor preizkusi in ti na podlagi programa oceni vajo.

videc ::

In? Sprogramiraj.
Tukaj ti ne bo nihče delal tvojega dela.

oslaj ::

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
 
using namespace std;
 
struct vozlisce
{
int utez;
int d;
int predhodnik;
int index;
};
 
char menu() {
    cout <<"Dijkstrov algoritem - izbira:"<<endl;
    cout <<"1 Vnos podatkov rocni"<<endl;
    cout <<"2 Zagon algoritma"<<endl;
    cout <<"3 Izpis najkrajše poti"<<endl;
    cout <<"4 Konec"<<endl;
    cout <<endl;
    cout <<"Vasa izbira:";
 
    string selection;
    do
        cin>>selection;
    while(selection.length() == 0);
    return selection[0];
}
 
void beriMatriko(int elementi[][100],int n)
{
        stringstream ss;
        string stevilazbesedo;
        cin.ignore();
        for (int i = 0; i < n; i++)
        {
            ss.clear ();
            ss.str ("");
            getline(cin, stevilazbesedo);
             ss.str (stevilazbesedo);
             for (int j = 0; j < n;j++)
             {
                    ss >> elementi[i][j];
             }
       }
}
 
 
int PoisciSoseda(int sosedje[][100],int ind,int st,int &nadaljuj)
{
            for(int j=nadaljuj;j<st;j++)
            {
                    if(sosedje[ind][j]<1000&&j!=ind)
                    {
                                          nadaljuj=j+1;
                                          cout<<"ff"<<j<<endl;
                                          return  j;
                    }
            }
            return -1;
}
 
vozlisce izloci_najmanjsega(vector<vozlisce> &Q)
{
  vozlisce najmanjse=Q.front();
  cout<<"prvo"<<najmanjse.d<<najmanjse.predhodnik<<endl;
 
    for(vector<vozlisce>::iterator i=Q.begin();i<Q.end();i++)
    {
           if(najmanjse.d>i->d)najmanjse=*i;
    }
 
    Q.erase(Q.begin()+najmanjse.index);
    return   najmanjse;
}
 
void Dijkstra(vozlisce V[],int s,int st_elementov,int sosedje[][100])
{
     int st_izlocenih=0;
     int ind=0,nadaljuj=0,w=0,vmesniw;
     bool prvi_sosed=true;
     vozlisce VOZ;
     vector<vozlisce> Q;
     for(int i=0;i<st_elementov;i++)
     {
                      V[i].d=1000;
                      V[i].predhodnik=-1;
                      V[i].index=i;
     }
 
     V[s].d=0;
     V[s].index=s;
 
     Q.clear();
     for(int i=0;i<st_elementov;i++)
     {
             Q.push_back(V[i]);
     }
 
     while(!Q.empty())//ponavljamo dokler ne obdelamo vseh v vrsti
     {
                      nadaljuj=0;
                      VOZ=izloci_najmanjsega(Q);
                      w=PoisciSoseda(sosedje,VOZ.index,st_elementov,nadaljuj);
                      while(w != -1)
                      {
                              if(Q[w].d > VOZ.d+ sosedje[VOZ.index][w])
                              {
                                           Q[w].d = VOZ.d+ sosedje[VOZ.index][w];
                                           Q[w].predhodnik = VOZ.index;
                              }
                              w=PoisciSoseda(sosedje,VOZ.index,st_elementov,nadaljuj);
                      }
     }
}
 
void izpisPoti(vozlisce V[],int s,int v)
{
 
    if (v==s)
    {
        cout <<s<<" globina: "<<V[s].d<< endl;
    }
    else if (V[v].predhodnik == -1)
    {
        cout <<"Med " << s << " in " << v << " ni poti " << endl;
    }
    else
    {
        izpisPoti(V,s,V[v].predhodnik);
        cout<<v<<": globina: "<<V[v].d<<endl;
    }
}
 
int main()
{
    istringstream ss;
    string stringec;
 
    int n=0,s=0,v=0;
    vozlisce V[20];
    int sosedje[100][100];
    bool running = true;
    char izbira;
 
    do {
       izbira = menu();
       switch (izbira) {
              case '1':
                   cout << "\nPodajte velikost tabele: "<<endl;
                   cin  >> n;
                   beriMatriko(sosedje,n);
                   break;
              case '2':
                   cout << "\nPodajte zacetno vozlisce: "<<endl;
 
                   getline(cin,stringec);
                    ss.clear();
                    ss.str(stringec);
                   ss>>ws>>s;
 
                   Dijkstra(V,s,n,sosedje);
                   break;
              case '3':
                   cout << "\nPodajte vozlisce v: "<<endl;
 
                    getline(cin,stringec);
                    ss.clear();
                    ss.str(stringec);
                   ss>>ws>>v;
 
                   izpisPoti(V,s,v);
                   break;
              case '4':
                   running = false;
                   break;
              default:
                   cout << "Napacna izbira!\n";
       }
    } while (running);
        return 0;
}


Evo ti samo pazi, da ne bo plagiat.

Tomaz3 ::

Če si ne znaš tega sam skupaj spesniti, ko imaš na internetu ogromno primerov, bi jaz na tvojem mestu začel razmišljati o menjavi faksa.

videc ::

Kaj je pa narobe rekel?

detroit ::

Če govoriva o Tomaz3-u potem vse. Ni na njegovem mestu da ubija voljo drugih. Nisem psiholog ampak vsakršno tlačenje drugih v govno kaže na manjko lastne samozavesti. Človek je prišel sem z vprašanjem in psevdo kodo. To pomeni da je začetno iniciativo imel, tudi ni rekel stipkajte mi kodo. Tale ST postaja kot 9gag...
Skero

Senitel ::

Jaz nisem ziher o začetni iniciativi. Psevdo koda je nekaj kar bi jim profesor/asistent na faksu odpredaval na tablo in jim potem dejansko dal za sprogramirat. Nismo dobili niti vrstice dejanske kode, povedano ni niti v katerem programskem jeziku se zadeva rešuje.

detroit ::

Vseeno, ali se mu pomaga ali pa se mu ne pomaga. Ne rabi se pa škodit z neumnimi izjavami s katerimi se zdravi lastne komplekse.
Skero

krneki0001 ::

rosetta code
http://rosettacode.org/wiki/Dijkstra's_...

class Graph
  Vertex = Struct.new(:name, :neighbours, :dist, :prev)
 
  def initialize(graph)
    @vertices = Hash.new{|h,k| h[k]=Vertex.new(k,[],Float::INFINITY)}
    @edges = {}
    graph.each do |(v1, v2, dist)|
      @vertices[v1].neighbours << v2
      @vertices[v2].neighbours << v1
      @edges[[v1, v2]] = @edges[[v2, v1]] = dist
    end
    @dijkstra_source = nil
  end
 
  def dijkstra(source)
    return  if @dijkstra_source == source
    q = @vertices.values
    q.each do |v|
      v.dist = Float::INFINITY
      v.prev = nil
    end
    @vertices[source].dist = 0
    until q.empty?
      u = q.min_by {|vertex| vertex.dist}
      break if u.dist == Float::INFINITY
      q.delete(u)
      u.neighbours.each do |v|
        vv = @vertices[v]
        if q.include?(vv)
          alt = u.dist + @edges[[u.name, v]]
          if alt < vv.dist
            vv.dist = alt
            vv.prev = u.name
          end
        end
      end
    end
    @dijkstra_source = source
  end
 
  def shortest_path(source, target)
    dijkstra(source)
    path = []
    u = target
    while u
      path.unshift(u)
      u = @vertices[u].prev
    end
    return path, @vertices[target].dist
  end
 
  def to_s
    "#<%s vertices=%p edges=%p>" % [self.class.name, @vertices.values, @edges] 
  end
end
 
g = Graph.new([ [:a, :b, 7],
                [:a, :c, 9],
                [:a, :f, 14],
                [:b, :c, 10],
                [:b, :d, 15],
                [:c, :d, 11],
                [:c, :f, 2],
                [:d, :e, 6],
                [:e, :f, 9],
              ])
 
start, stop = :a, :e
path, dist = g.shortest_path(start, stop)
puts "shortest path from #{start} to #{stop} has cost #{dist}:"
puts path.join(" -> ")


rezultat
shortest path from a to e has cost 20:
a -> c -> f -> e
Asrock X99 Extreme 4 | Intel E5-2683V4 ES | 64GB DDR4 2400MHz ECC |
Samsung 250GB M.2 | Asus 1070 TI | 850W Antec | LC Tank Buster


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

[C#] Sort za string (slovenska abeceda)

Oddelek: Programiranje
5882 (691) mihies
»

Kruskalov algoritem težave pri implementaciji

Oddelek: Programiranje
51527 (1301) zacetnik11
»

[C++ naloga] seznam

Oddelek: Programiranje
81334 (1334) BigWhale
»

[c++] dvosmerno povezan seznam

Oddelek: Programiranje
122471 (2307) upirna
»

win api (c++)

Oddelek: Programiranje
462421 (1701) Gundolf

Več podobnih tem