Penelitian ini bertujuan untuk mengetahui kemampuan komunikasi matematis dan habits of mind mahasiswa, hal ini dilakukan sesuai dengan rekomendasi CUPM yang menyatakan bahwa setiap perkuiahan harus mencakup kegiatan yang akan membantu semua mahasiswa untuk mengebangkan daya analitis, penalaran kritis, pemecahan masalah, dan kemampuan berkomunikasi. Tujuan selanjutnya dari penelitian ini adalah untuk memperoleh gambaran kendala yang dihadapi mahasiswa dalam memanfaatkan software Algoritma Floyd Warshall. Penelitian ini merupakan penelitian deskripsi-kualitatif. Subjek penelitian berjumlah 4 orang yaitu mahasiswa Program Studi Pendidikan Matematika FKIP Unsyiah yang mengambil matakuliah Teori Graf tahun ajaran 2012/2013. Pemilihan subjek dilakukan berdasarkan hasil pengamatan aktivitas mahasiswa dalam pembelajaran yaitu mahasiswa yang aktif, kurang aktif dan tidak aktif serta memiliki IPK lebih dari tiga. Data hasil penelitian diperoleh dari pengamatan, jawaban tertulis dan hasil wawancara. Untuk menguji kredibelitas data peneliti melakukan triangulasi. Dalam penelitian ini, triangulasi yang dipakai adalah triangulasi metode yaitu dengan cara membandingkan jawaban tertulis dengan data hasil pengamatan dan data hasil wawancara. Kemampuan komunikasi matematis mahasiswa dapat dilihat berdasarkan perolehan indikator rubrik. Kemampuan komunikasi matematis mahasiswa yang diteliti sebagai berikut, tingkat kemampuan komunikasi matematis subjek I adalah cukup baik, tingkat kemampuan komunikasi matematis subjek II adalah sangat baik, tingkat kemampuan komunikasi matematis subjek III adalah baik, dan tingkat kemampuan komunikasi matematis subjek IV adalah cukup baik. Habits of Mind yang ditunjukkan subjek penelitian adalah sebagai berikut; subjek I menunjukkan Habits of mind yang kurang maksimal, subjek II menunjukkan habits of mind yang sangat baik, subjek III menunjukkan habits of mind yang sangat baik, dan subjek IV menunjukkan habits of mind yang cukup baik. Sedangkan kendala mahasiswa dalam memanfaatkan software Algoritma Floyd Warshall adalah, 1) graf/digraf tidak dapat diperbaiki bila sudah diproses (dijalankan), 2) hasil kerja dengan menggunakan software tidak dapat disimpan, 3) verteks yang dapat digunakan terbatas, dan 4) tidak ada informasi jarak antara suatu tempat ke tempat yang lain, sehingga kurang dapat dimanfaatkan dalam kehidupan nyata. Kata kunci: Kemampuan komunikasi matematis, habits of mind, lintasan terpendek, Algoritma Floyd Warshall.