Dijkstra's Algorithm: Minimalist(!) C# Implementation

Hi all, In a previous post, I mentioned that I will challenge myself for writing Dijkstra's algorithm with minimum lines of code. The C# code is here as promised. Now first of all, this is possibly the worst implementation that can be done; and the only intention was to really do things in a short way in terms of Number of Lines used. The code is not maintainable and not even readable. Well, the trick comes from maintaining only a distance array and calculating all other stuff wherever required. My first version of this code was 8 lines (I was separately holding a list of nodes that was not reached) but then I realized that it was possible to calculate it using the distance array each time. Before going into the code let me introduce you the basic idea of the algorithm as I implemented.
As previously mentioned all edges have positive costs. Also we assume that the graph is connected. Let N be the nodes, i the source and j the sink node, A the distance matrix.
  • Maintain two lists U = {i} , V = N \ {i}
  • Set d[i] = 0 distance of i to i
  • While j is not reached
  • Find s in U, t in V such that d[s] + A[s,t] is minimum
  • Set d[t] = d[s] + A[s,t]
  • Take t from V and put to U
  • if t is j return dist[t]
Well, my code is even shorter than my pseudo-code. Here is the 4 line Dijkstra implementation (not counting the function definition and the closing bracket):
public static double DijkstraMinimal(double[,] A, int i, int j){
double[] dist = Enumerable.Range(0, A.GetLength(0)).ToList().Select(k => k==i ? 0.0 : -1.0).ToArray();
while (true){
dist[(Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Select(k => new { idx = k, len = Enumerable.Range(0, A.GetLength(0)).Select(t => Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Contains(t) ? double.MaxValue : dist[t] + A[t, k]).Min() }).First(t => t.len == Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Select(k => new { idx = k, len = Enumerable.Range(0, A.GetLength(0)).Select(m => Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Contains(m) ? double.MaxValue : dist[m] + A[m, k]).Min() }).Min(z => z.len))).idx] = (Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Select(k => new { idx = k, len = Enumerable.Range(0, A.GetLength(0)).Select(t => Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Contains(t) ? double.MaxValue : dist[t] + A[t, k]).Min() }).First(t => t.len == Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Select(k => new { idx = k, len = Enumerable.Range(0, A.GetLength(0)).Select(m => Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Contains(m) ? double.MaxValue : dist[m] + A[m, k]).Min() }).Min(z => z.len))).len;
if ((Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Select(k => new { idx = k, len = Enumerable.Range(0, A.GetLength(0)).Select(t => Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Contains(t) ? double.MaxValue : dist[t] + A[t, k]).Min() }).First(t => t.len == Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Select(k => new { idx = k, len = Enumerable.Range(0, A.GetLength(0)).Select(m => Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Contains(m) ? double.MaxValue : dist[m] + A[m, k]).Min() }).Min(z => z.len))).idx == j) return dist[j];}
}
The 4th line is 1150 characters. Lets put this into a more readable form, thanks to Resharper:
public static double DijkstraMinimalReadable(double[,] A, int i, int j)
{
double[] dist = Enumerable.Range(0, A.GetLength(0)).ToList().Select(k => k == i ? 0.0 : -1.0).ToArray();
while (true)
{
dist[
(Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Select(
k =>
new
{
idx = k,
len =
Enumerable.Range(0, A.GetLength(0)).Select(
t =>
Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Contains(t)
? double.MaxValue
: dist[t] + A[t, k]).Min()
}).First(
t =>
t.len ==
Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Select(
k =>
new
{
idx = k,
len =
Enumerable.Range(0, A.GetLength(0)).Select(
m =>
Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).
Contains(m)
? double.MaxValue
: dist[m] + A[m, k]).Min()
}).Min(z => z.len))).idx] =
(Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Select(
k =>
new
{
idx = k,
len =
Enumerable.Range(0, A.GetLength(0)).Select(
t =>
Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Contains(t)
? double.MaxValue
: dist[t] + A[t, k]).Min()
}).First(
t =>
t.len ==
Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Select(
k =>
new
{
idx = k,
len =
Enumerable.Range(0, A.GetLength(0)).Select(
m =>
Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).
Contains(m)
? double.MaxValue
: dist[m] + A[m, k]).Min()
}).Min(z => z.len))).len;
if (
(Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Select(
k =>
new
{
idx = k,
len =
Enumerable.Range(0, A.GetLength(0)).Select(
t =>
Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Contains(t)
? double.MaxValue
: dist[t] + A[t, k]).Min()
}).First(
t =>
t.len ==
Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).Select(
k =>
new
{
idx = k,
len =
Enumerable.Range(0, A.GetLength(0)).Select(
m =>
Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).
Contains(m)
? double.MaxValue
: dist[m] + A[m, k]).Min()
}).Min(z => z.len))).idx == j)
return dist[j];
}
}
And now a much more efficient implementation of the same thing without recalculations. I don't ever say that it is efficient, but it is just more efficient. The best way would be maintaining the both lists outside of the while loop and removing and inserting necessary elements before continuing.
public static double DijkstraMinimalEff(double[,] A, int i, int j)
{
double[] dist = Enumerable.Range(0, A.GetLength(0)).ToList().Select(k => k == i ? 0.0 : -1.0).ToArray();
while (true)
{
List<int> notfound = Enumerable.Range(0, A.GetLength(0)).Where(l => dist[l] == -1.0).ToList();
var x = notfound.Select(k => new { idx = k, len = Enumerable.Range(0, A.GetLength(0)).Select(t => notfound.Contains(t) ? double.MaxValue : dist[t] + A[t, k]).Min() }).First(t => t.len == notfound.Select(k => new { idx = k, len = Enumerable.Range(0, A.GetLength(0)).Select(m => notfound.Contains(m) ? double.MaxValue : dist[m] + A[m, k]).Min() }).Min(z => z.len));
dist[x.idx] = x.len;
if (x.idx == j) return x.len;
}
}
I had great fun writing the 1150 char. line, hope all these were funny for you, too. Take good care, Baris

58 yorum:

Unknown dedi ki...

I feel really happy to have seen your webpage and look forward to so many more entertaining times reading here. Thanks once more for all the details.

big data training in chennai

Anoushka Sakthi dedi ki...

I am a regular reader of your blog, Amazing content with proper examples. Thank you admin.
Loadrunner Training in Chennai
Big Data Training in Chennai
Digital Marketing Chennai
Digital Marketing Training in Chennai
Digital Marketing Chennai

cynthiawilliams dedi ki...

Useful content, I have bookmarked this page for my future reference.
AWS Training in Chennai
AWS course in Chennai
AWS Certification in Chennai
Angularjs Training in Chennai
DevOps Training in Chennai
RPA Training in Chennai

Anbarasan14 dedi ki...

Thanks for your contribution in sharing such a useful information. this was really helpful to me. Waiting for your further updates.

Spoken English Institute in Porur | Spoken English Classes in Mugalivakkam | Spoken English Training in Iyyappanthangal | Spoken English Training in Poonamallee | Spoken English Training in Kolapakkam | Spoken English in Porur

vishnu dedi ki...

Your blog is very useful to me. Keep up the good work.

Placement Training institutes in Chennai |Best placement Training institutes in Chennai | Training come placement in Chennai | Placement courses in Chennai | Training and job placement in Chennai | Placement Training in Chennai

pavithra dass dedi ki...

Hi,
I must appreciate you for providing such a valuable content for us. This is one amazing piece of article. Helped a lot in increasing my knowledge.
Cloud computing Training in Chennai
Cloud computing courses in Chennai
Cloud Training in Chennai
Best institute for Cloud computing in Chennai
Cloud computing Training Chennai

Unknown dedi ki...
Bu yorum yazar tarafından kaldırıldı.
Unknown dedi ki...


Useful content. Thanks for Sharing. It shows your indepth knowledge on the subject. Pls keep updating.
Tableau Advanced Training

Tableau Software Training


Tableau Training in Velachery

mercyroy dedi ki...

More informative,thanks for sharing with us.this blog makes the readers more enjoyable.keep add more info on your page.
Best Java Training Institutes in Bangalore with 100 placement
Java Training in Mogappair
Java Training in Ashok Nagar
Java Training in Kelambakkam

Aruna Ram dedi ki...

Nice articles posted. It's useful for developing my skill. Keep sharing the articles!!!
Data Science Training in Velachery
Data Science Training in Tambaram
Data Science Training in Chennai Velachery
Data Science Training in Tnagar
Data Science Training in Nungambakkam

Unknown dedi ki...

Great post! This is very useful for me and gain more information, Thanks for sharing with us.
Spoken English Course in Chennai
English Speaking Course in Chennai
Spoken English Training center in Chennai
Spoken English Classes in Anna Nagar

LindaJasmine dedi ki...

Amazing Blog. I liked your style of writing. Pls keep on writing.

Drupal 7 Training
Drupal Certification Training
Drupal Training Course
Drupal 7 Certification
Drupal Training in Velachery

Unknown dedi ki...

I am feeling great to read this.you gave a nice info for us.
please update more.
AWS Training center in Bangalore
AWS Training in Ambattur
AWS Training in Saidapet

Unknown dedi ki...

It is very excellent blog and useful article thank you for sharing with us, keep posting.
Ethical Hacking Training in Velachery
Ethical Hacking Courses in Velachery
Ethical Hacking Training in Tambaram
Ethical Hacking Training in Adyar
Ethical Hacking Courses in Adyar

Unknown dedi ki...

Thank you for such amazing post. Keep up the good work.

SAS Training in Chennai
SAS Course in Chennai
SAS Training Institutes in Chennai
SAS Institute in Chennai
SAS Training Chennai
SAS Training Institute in Chennai
SAS Courses in Chennai

LindaJasmine dedi ki...

Amazing Post. It shows your great in-depth knowledge on the topic. Thanks for Posting. You are a life-saver.

Node JS Training in Chennai
Node JS Course in Chennai
Node JS Advanced Training
Node JS Training Institute in chennai
Node JS Training Institutes in chennai
Node JS Course

Aruna Ram dedi ki...

One of the best blogs that i have read still now. Thanks for your contribution in sharing such a useful information. Waiting for your further updates.
PHP Course in Aminjikarai
PHP Training in Vadapalani
PHP Training in Chennai
PHP Course in Padur
PHP Training in Kandanchavadi
PHP Course in Sholinganallur

Vicky Ram dedi ki...

It is a great post. Keep sharing such kind of useful information.

Article submission sites
Guest posting sites

Aruna Ram dedi ki...

Amazing post!!! This post is very useful for me. Truly well post. Kindly keep updating more.....
Blue Prism Training in Bangalore
Blue Prism Training Bangalore
Blue Prism Classes in Bangalore
Blue Prism Training in Chennai Adyar
Blue Prism Course in Annanagar
Blue Prism Training in Annanagar

Aruna Ram dedi ki...

Nice articles posted. Keep sharing the articles. I appreciate you sharing this article. Really thank you!
Web Designing Training in Vadapalani
Web Designing course in Chennai kknagar
Web Designing Course in Chennai
Web Designing Course in Padur
Web Designing Course in Tambaram
Web Designing Classes near me

Aruna Ram dedi ki...

It was really great! I learn lot of information from your post. I want more updates.....
Machine Learning Training in Velachery
Machine Learning Training in Chennai Velachery
Machine Learning Course in Tnagar
Machine Learning Training in Nungambakkam
Machine Learning Course in Saidapet

VenuBharath2010@gmail.com dedi ki...


Extra-Ordinary. The way the blog was written is amazing. Waiting for your next post.
Xamarin Training in Chennai
Xamarin Course in Chennai
Xamarin Training
Xamarin Course
Xamarin Training Course
Xamarin Classes
Best Xamarin Course
Xamarin Training Institute in Chennai
Xamarin Training Institutes in Chennai

Kayal dedi ki...

Your post is very nice and it's very useful for enhance my knowledge. Thanks for your worthy concept.
CCNA Training in Tambaram
CCNA Training in Chennai Velachery
CCNA Training in Tnagar
CCNA Course in Vadapalani
CCNA Training in Nungambakkam
CCNA Course in Kodambakkam

WUGI dedi ki...

Only here are the best winnings Online casinos Gaming casino.

jefrin dedi ki...

Very useful post thanks for sharing
Tableau training in chennai

abhi pranesh dedi ki...

Really an awesome post for every one.
German Classes in Chennai
German language training in chennai
IELTS Coaching in Chennai
Japanese Classes in Chennai
spanish language in chennai
Spoken English Classes in Chennai
German Language Course in Chennai
German Language Classes in Chennai

Vicky Ram dedi ki...

Enjoyed your approach to explaining how it works, hope to see more blog posts from you. thank you!

Article submission sites
Guest posting sites

Manipriyan dedi ki...

Extra-Ordinary. The way the blog was written is amazing. Waiting for your next post.


IOT Training in Chennai

PHP Training in Chennai

Wordpress Training in Chennai

luckys dedi ki...

age calculator

tech zone dedi ki...

imo for pc

Jackie Co Kad dedi ki...

Great Article
IEEE Projects on Cloud Computing
Final Year Projects for CSE


JavaScript Training in Chennai
JavaScript Training in Chennai

saathvik kutta dedi ki...

This is good information and really helpful for the people who need information about this.
personalized mugs online india
print cup online india
rent laptop chennai
computer rental in chennai
company registration consultants in chennai
private limited company registration in chennai

akalya dedi ki...

good..

internship for bba students

internship certificate for cse students

internship training in chennai

internships in hyderabad for cse students 2020

r training in chennai

robotics course

internship for ece students in core companies

internship for aeronautical engineering students in bangalore

internship for cse students in bangalore 2019

industrial visits for college students in chennai

akalya dedi ki...

nice..

how to hack chromebook using crosh

hack tp link wifi username and password

brac ngo written test question

whatsapp ethical hacking

react js developer resume india

integer max value javascript

binatone wifi hack

a certain sum of money amounts to rs.1300 in 2 years and to rs. 1525 in 3.5 years. find the sum and the rate of interest

she spent most of her time tomusic

she most of her time tomusic

Galia Co Hagan dedi ki...

Great Article. Thank you for sharing! Really an awesome post for every one.

IEEE Final Year projects Project Centers in Chennai are consistently sought after. Final Year Students Projects take a shot at them to improve their aptitudes, while specialists like the enjoyment in interfering with innovation. For experts, it's an alternate ball game through and through. Smaller than expected IEEE Final Year project centers ground for all fragments of CSE & IT engineers hoping to assemble. Final Year Project Domains for IT It gives you tips and rules that is progressively critical to consider while choosing any final year project point.

JavaScript Training in Chennai

JavaScript Training in Chennai


hari dedi ki...

good..
inplant training in chennai
inplant training in chennai for it
Bermuda web hosting
Botswana hosting
armenia web hosting
dominican republic web hosting
iran hosting
palestinian territory web hosting
iceland web hosting

hari dedi ki...

nice
inplant training in chennai
inplant training in chennai for it
suden web hosting
tunisia hosting
uruguay web hosting
Bermuda web hosting
Botswana hosting
armenia web hosting
lebanon web hosting

hari dedi ki...

good
Bermuda web hosting
Botswana hosting
armenia web hosting
lithuania shared web hosting
inplant training in chennai
inplant training in chennai for it
suden web hosting
tunisia hosting
uruguay web hosting

hari dedi ki...

good
inplant training in chennai
inplant training in chennai
online python internship
online web design
online machine learning internship
online internet of things internship
online cloud computing internship
online Robotics
online penetration testing

shri dedi ki...

Awesome nice post...
internship report on python
free internship in chennai for ece students
free internship for bca
internship for computer science engineering students in india
internships in hyderabad for cse students 2018
electrical companies in hyderabad for internship
internships in chennai for cse students 2019
internships for ece students
inplant training in tcs chennai
internship at chennai

Muthu dedi ki...

Nice Infromation....
internship in chennai for ece students with stipend
internship for mechanical engineering students in chennai
inplant training in chennai
free internship in pune for computer engineering students
internship in chennai for mca
iot internships
internships for cse students in hyderabad
implant training in chennai
internship for aeronautical engineering students in bangalore
inplant training certificate

sugan dedi ki...

very nice post.........
r programming training in chennai
internship in bangalore for ece students
inplant training for mechanical engineering students
summer internships in hyderabad for cse students 2019
final year project ideas for information technology
bba internship certificate
internship in bangalore for ece
internship for cse students in hyderabad
summer training for ece students after second year
robotics courses in chennai

Muthu dedi ki...

http://blog.bariscemsal.net/2011/02/dijkstra-algorithm-minimalist-c.html?showComment=1573466160284#c355846954831094785

Muthu dedi ki...

Nice post...
3d-modeler-resume-samples
3d modeler resume samples
accounting-assistant-resume-sample
accounting-clerk-resume-sample
accounting-manager-resume-samples
account-manager-resume-examples
accounts-payable-resume-sample
admin-manager-resume-samples
advocate-resume-sample
advocate-resume-sample

sibiselvan dedi ki...

it is good blogs!!!

paid internships in pune for computer science students
machine learning training in chennai
data science internship in chennai
dot net training in chennai
kaashiv infotech chennai
internship for aeronautical engineering students in india
internship in automobile industry
big data internship in chennai
machine learning internship in chennai
internship in chennai for it students

reena dedi ki...

Nice
To gain work experience
To Choosing your career
To gain skills
To help you become more self-confident.....
branch-operations-manager-resume-samples
business-executive-resume-samples
business-owner-resume-samples
business-to-business-sales-resume-sample-sales-resumes
cad-design-engineer-resume-samples
call-centre-jobs-resume-sample
ca-resume-samples-chartered-accountant-resume-format
cassandra-database-administrator-resume
category/accountant-resume
category/admin-resume

shalini dedi ki...

good....nice
category/advocate-resume
category/agriculture-forestry-fishing
category/android-developer-resume
category/assistant-professor-resume
category/chartered-accountant-resume
category/database-resume
category/design-engineer-resume
category/developer-resume
category/engineer-resume
category/entrepreneur-and-financial-services-resume

Praisy Margret dedi ki...

good..nice..
assistant-director-resume-format
assistant-director-resume-sample
assistant-professor-resume-sample
back-office-executive-resume-samples
bank-branch-manager-resume-samples
basketball-coach-resume-sample-coach-resumes
bca-fresher-resume-sample
best-general-manager-resume-example
bpo-resume-freshers-sample
bpo-resume-samples-for-freshers

reena dedi ki...

good ....nice...
resume/category/software-testing-resume
resume/category/sslc-resume
resume/category/storekeeper-resume
resume/category/stylist-resume
resume/category/teachers-resume
resume/category/technical-architect-resume
resume/category/web-developer-resume
cics-system-programmer-resume-example
resume/cisco-network-engineer-resume
resume/cisco-network-engineer-resume-sample

shalini dedi ki...

good.....nice..
category/maintenance-resume
category/manager-resume
category/mechanical-engineering-resume
category/network-engineer-resume
category/officer-resume
category/operations-resume
category/process-associate-resume
category/quality-control-resumes
category/software-engineer-resume

Praisy Margret dedi ki...

good... nice... very useful..
assistant-director-resume-format
director-resume-sample
assistant-professor-resume-sample
back-office-executive-resume-samples
bank-branch-manager-resume-samples
basketball-coach-resume-sample-coach-resumes
bca-fresher-resume-sample
best-general-manager-resume-example
bpo-resume-freshers-sample
bpo-resume-samples-for-freshers

reena dedi ki...



film-director-resume
finance-and-accounting-manager-resume-samples
finance-director-resume-examples
fire-safety-officer-resume-sample
fleet-maintenance-manager-resume-samples
format-for-resume-writing
fresher-computer-engineers-resume-sample
fresher-hr-resume-sample
fresher-hr-resume-sample-2
fresher-lecturer-resume


Unknown dedi ki...

it is best blogs ....

civil-engineer-resume-format
client-service-executive-resume-sample
cognos-developer-resume-samples
college-lecturer-resume
college-lecturer-resume-sample
commercial-assistant-resume-sample
compliance-officer-resume-samples
computer-teacher-resume-format
computer-teacher-resume-sample
cordova-developer-resume-sample

sasi dedi ki...

It's a very awesome article! Thanks a lot for sharing information.
python training in hyderabad
Python Training in Bangalore
Python Training in Coimbatore
Python Training in Chennai
web designing course in bangalore
salesforce course in bangalore
Best Python Training in Bangalore
Python course in bangalore
python training in marathahalli
Python Classes in Bangalore

dhishageetha dedi ki...


This Blog is really informative!! keep update more about this...
Aviation Academy in Chennai
Air Hostess Training in Chennai
Airport Management Courses in Chennai
Best Aviation Academy in Chennai
Ground Staff Training in Chennai
Air Hostess Academy in Chennai
Airport Management Training in Chennai
Airport Ground Staff Training Courses in Chennai

saran dedi ki...

"Thanks for sharing..

Digital Marketing Training Course in Chennai | Digital Marketing Training Course in Anna Nagar | Digital Marketing Training Course in OMR | Digital Marketing Training Course in Porur | Digital Marketing Training Course in Tambaram | Digital Marketing Training Course in Velachery

"

cathrine juliet dedi ki...

Thank you for the informative post. It was thoroughly helpful to me. Keep posting more such articles and enlighten us.

Big Data Hadoop Training In Chennai | Big Data Hadoop Training In anna nagar | Big Data Hadoop Training In omr | Big Data Hadoop Training In porur | Big Data Hadoop Training In tambaram | Big Data Hadoop Training In velachery

vivekvedha dedi ki...

Greetings! Very helpful advice in this particular post! It is the little changes that produce the most significant changes. Many thanks for sharing!
Digital Marketing Training Course in Chennai | Digital Marketing Training Course in Anna Nagar | Digital Marketing Training Course in OMR | Digital Marketing Training Course in Porur | Digital Marketing Training Course in Tambaram | Digital Marketing Training Course in Velachery

Yorum Gönderme