帮做Python and Applications、代写Python编程语言、帮做Python程序、Python设计留学生代做

日期：2018-10-02 10:32

Assignment #2

Professor Ahmad Namini

Python and Applications to Business Analytics Fall 2018, Module 1

September 25, 2018

Exercise 1. Below is the code for Dijkstra’s Algorithm for computing the smallest cost

along some path which is modeled as a weighted graph.

Input consists of nodes and costs. The hard-coded input is that of the graph from your

notes.

Output is the variable visited nodes which represents the least cost path from a given

start node to other nodes.

Please note that I have inserted commented print statements to follow the flow and

data of the algorithm. Printing variable names during execution of code is a great way

to understand the flow and data changes during the execution of your code. Another

way is to use your IDE’s debugger, but unfortunately, each IDE has a different flavor

to what and how a debugger works. I would suggest investing time in understanding

how your IDE’s debugger works.

The foreign exchange (FX) market, where one currency is traded for another, is the largest

financial market in the world, with about 5 trillion USD being traded every day. This market

determines the exchange rate for local currencies when someone travels abroad and when

international banks settle accounts between each other.

Let’s model a currency exchange’s FX rates as a weighted graph, where each node represents

a currency (e.g. CNY, JPY, USD) and each edge represents the conversion of currency A to

currency B. The weighted graph’s edge cost is the FX conversion rate between the two end

currencies.

At the following site, Wells Fargo shows current FX rates between many currencies and

the US dollar. Dealers in the FX market will usually add or subtract a percentage of the

FX rate depending on whether the client is selling a currency (the Bid rate) or buying a

currency (the Ask rate).

An arbitrage condition exists when you can buy in one currency and sell in another currency

and make a risk-less profit.

Using Dijkstra’s Algorithm, do the following:

1

? Model the FX market rates as a weighted graph for the following currencies (CNY,

JPY, EUR, USD, GBP, CAD)

? Model bid and ask rates as a percentage of FX rates. Use 1, 2, and 5 percents on the

bid side, and 1, 2, and 5 percent on the ask side. This gives nine different scenarios.

? Check whether an arbitrage condition exists. (Think about how best to do this.)

? Make your output so that anyone requiring to understand the markets for arbitrage

can understand from your output what the results are.

# D i j k s t r a ’ s A l g o r i t hm

#

# An a l g o r i t h m f o r f i n d i n g t h e l e a s t c o s t p a t h b e t w e e n n o d e s i n a g r a p h .

# I t was c o n c e i v e d b y com pu t e r s c i e n t i s t E d s g e r W. D i j k s t r a i n 1 9 5 6 .

# n e t w o r k t o p o l o g y and c o s t s

nod es = ( ’ a ’ , ’ b ’ , ’ c ’ , ’ d ’ , ’ e ’ , ’ f ’ )

c o s t s = { ’ a ’ : { ’ b ’ : 7 , ’ c ’ : 9 , ’ f ’ : 14} ,

’ b ’ : { ’ a ’ : 7 , ’ c ’ : 1 0 , ’ d ’ : 15} ,

’ c ’ : { ’ a ’ : 9 , ’ d ’ : 1 1 , ’ f ’ : 2} ,

’ d ’ : { ’ b ’ : 1 5 , ’ c ’ : 1 1 , ’ e ’ : 6} ,

’ e ’ : { ’ d ’ : 6 , ’ f ’ : 9} ,

’ f ’ : { ’ a ’ : 1 4 , ’ c ’ : 2 , ’ e ’ : 9}}

s t a r t n o d e = ’ a ’

# i n i t i a l i z e f o r D i j k s t r a ’ s a l g o r i t h m

u n v i s i t e d n o d e s = {node : None fo r node in nod es }

v i s i t e d n o d e s = {}

c u r r e n t n o d e = s t a r t n o d e

c u r r e n t c o s t = 0

u n v i s i t e d n o d e s [ c u r r e n t n o d e ] = c u r r e n t c o s t

# a p p l y a l g o r i t h m

while True :

# p r i n t(”??????????????????????????????????”)

# p r i n t ( ” u n v i s i t e d t o s t a r t : ” )

# p r i n t ( u n v i s i t e d n o d e s )

fo r n e i ghb o r , c o s t in c o s t s [ c u r r e n t n o d e ] . i t em s ( ) :

# p r i n t (”{0} {1} {2}” . f o rm a t ( c u r r e n t n o d e , n e i g h b o r , c o s t ) )

i f n e i g h b o r not in u n v i s i t e d n o d e s :

continue

n ew c o s t = c u r r e n t c o s t + c o s t

i f u n v i s i t e d n o d e s [ n e i g h b o r ] i s None or n ew c o s t < u n v i s i t e d n o d e s [ n e i g h b o r ] :

u n v i s i t e d n o d e s [ n e i g h b o r ] = n ew c o s t

# p r i n t ( ” u n v i s i t e d : ” )

# p r i n t ( u n v i s i t e d n o d e s )

v i s i t e d n o d e s [ c u r r e n t n o d e ] = c u r r e n t c o s t

# p r i n t ( ” v i s i t e d : ” )

# p r i n t ( v i s i t e d n o d e s )

de l u n v i s i t e d n o d e s [ c u r r e n t n o d e ]

i f not u n v i s i t e d n o d e s :

break

c a n d i d a t e s = [ node fo r node in u n v i s i t e d n o d e s . i t em s ( ) i f node [ 1 ] ]

c u r r e n t n o d e , c u r r e n t c o s t = sorted ( c a n d i d a t e s , key = lambda x : x [ 1 ] ) [ 0 ]

# p r i n t ( ” c a n d i d a t e s : ” )

# p r i n t ( c a n d i d a t e s )

# p r i n t ( ” c u r r e n t n o d e , c u r r e n t c o s t : ” )

# p r i n t ( c u r r e n t n o d e , c u r r e n t c o s t )

# p r i n t n o d e s w i t h l e a s t c o s t s

pr int ( v i s i t e d n o d e s )