codes en macros

[Esthetisch]

Een code zoals deze:

procedure BellmanFord(list vertices, list edges, vertex source)

   // This implementation takes in a graph, represented as lists of vertices and edges,

   // and fills two arrays (distance and predecessor) with shortest-path information

   // Step 1: initialize graph

   for each vertex v in vertices:

       if v is source then distance[v] := 0

       else distance[v] := infinity

       predecessor[v] := null

   // Step 2: relax edges repeatedly

   for i from 1 to size(vertices)-1:

       for each edge (u, v) with weight w in edges:

           if distance + w < distance[v]:

               distance[v] := distance + w

               predecessor[v] := u

   // Step 3: check for negative-weight cycles

   for each edge (u, v) with weight w in edges:

       if distance + w < distance[v]:

           error "Graph contains a negative-weight cycle"

Afkomstig van: http://en.m.wikipedi...3Ford_algorithm

Voor welk programma is de code geschreven? Hoe kun je de code uitvoeren? Hoe geef je de input?

Maar m'n voornaamste vraag: valt deze code (makkelijk) om te zetten naar een code voor bij een excelmacro??

[Math-E-Mad-X]

Dit is geen echte programmeer taal, maar pseudo-code. dat wil zeggen dat het zodanig genoteerd is dat vrijwel iedere programmeur het begrijpt, onafhankelijk van welke programmeertaal hij of zij gewend is mee te werken. Bovendien is het vrij eenvoudig om deze code te vertalen naar de meeste bekende programmeertalen zoals java, C++ of C#.

Ik ben niet bekend met excel macro's, maar ik neem aan dat daarmee net zo eenvoudig gaat.

Je kunt deze code dus niet direct uitvoeren, maar je moet hem eerst herschrijven in een echte programmeertaal.

Het antwoord op deze vraag:

Hoe geef je de input?

Staat hier:

// This implementation takes in a graph, represented as lists of vertices and edges,

Je voert dus twee lijsten in. De ene representeerd de vertices (dat zal gewoon een lijst met de getallen van 1 tot n zijn, als je n vertices hebt) en een lijst die alle weights w bevat, voor iedere edge (dit zou ik zelf overigens eerder als een matrix implementeren dan als een lijst, maar dat doet er niet zo veel toe).

[Esthetisch]

Ok bedankt, het is me duidelijk, ik ga ermee aan de slag.

Nog even een vraagje puur uit interesse:

en een lijst die alle weights w bevat, voor iedere edge

Hoe geef je in die tweede lijst dan aan bij welke edge een weight hoort? Geef je de edge gewoon de naam van zijn punten, dus dat het er als volgt uit komt te zien

Edges

AB 14

AC 19

AD 21

BC 13

.

.

.

Of is het toch nog anders?

[Math-E-Mad-X]

Ik zou het als een matrix (oftewel een dubbele lijst) implementeren:

weights[0][1] = 14

weights[0][2] = 19

weights[0][3] = 21

weights[1][2] = 13

[Xenion]

Een lijst van koppels is meestal een goeie representatie. Een matrix maakt het in mijn ogen moeilijker om er dan achteraf mee te werken, omdat je dan steeds moet scannen naar niet nulle elementen in die matrix terwijl je met een lijst meteen weet hoeveel edges er precies bestaan.

Bijvoorbeeld edges = ( [a,b], [b,c] ) om aan te geven dat er edges bestaan tussen a en b en tussen b en c.

Voor de weights kan je eventueel een nieuwe lijst maken die dezelfde lengte heeft als de edge lijst of je zet dit gewoon bij in de edge lijst als edges = ([a,b,w1],[b,c,w2]).