DIJKSTROV_ALGORITEM

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!

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

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

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

#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.

Kaj je pa narobe rekel?

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.

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